Time complexity of this function

Question

I am pretty sure about my answer but today had a discussion with my friend who said I was wrong.

I think the complexity of this function is O(n^2) in average and worst case and O(n) in best case. Right?

Now what happens when k is not length of array? k is the number of elements you want to sort (rather than the whole array).

Is it O(nk) in best and worst case and O(n) in best case?

Here is my code:

#include <stdio.h>

void bubblesort(int *arr, int k)
{
    // k is the number of item of array you want to sort
    // e.g. arr[] = { 4,15,7,1,19} with k as 3 will give
    // {4,7,15,1,19} , only first k elements are sorted
  int i=k, j=0;
  char test=1;
  while (i && test)
  {
    test = 0;
    --i;
    for (j=0 ; j<i; ++j)
    {
      if ((arr[j]) > (arr[j+1]))
      {
          // swap 
          int temp = arr[j];
          arr[j]=arr[j+1];
          arr[j+1]=temp;
        test=1;
      }

    }  // end for loop

  } // end while loop
}

int main()
{

    int i =0;
    int arr[] = { 89,11,15,13,12,10,55};
    int n = sizeof(arr)/sizeof(arr[0]);

    bubblesort(arr,n-3);
    for (i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}

P.S. This is not homework, just looks like one. The function we were discussing is very similar to Bubble sort. In any case, I have added homework tag.

Please help me confirm if I was right or not. Thank you for your help.

O(n2) and O(n) are the same thing, any constant factor is usally ignored... also, did you have a look at the wikipedia article bout bubblesort? — PlasmaHH
– PlasmaHH, Commented Nov 11, 2011 at 15:00
@PlassmaHH , Sorry, did you mean O(n^2) and O(nk) are same thing? — Ian McGrath
– Ian McGrath, Commented Nov 11, 2011 at 15:03
@Kevin, oh now I see what caused the confusion. I will edit that. Thanks, yes, that is what I meant — Ian McGrath
– Ian McGrath, Commented Nov 11, 2011 at 15:03

Werner Henze · Accepted Answer · 2011-11-11 15:05:26Z

Complexity is normally given as a function over n (or N), like O(n), O(n*n), ...

Regarding your code the complexity is as you stated. It is O(n) in best case and O(n*n) in worst case.

What might have lead to misunderstanding in your case is that you have a variable n (length of array) and a variable k (length of part in array to sort). Of course the complexity of your sort does not depend on the length of the array but on the length of the part that you want to sort. So with respect to your variables the complexity is O(k) or O(k*k). But since normally complexity notation is over n you would say O(n) or O(n*n) where n is the length of the part to sort.

JoeG · Accepted Answer · 2011-11-11 15:04:58Z

2

Is it O(nk) in best and worst case and O(n) in best case?

No, it's O(k^2) worst case and O(k) best case. Sorting the first k elements of an array of size n is exactly the same as sorting an array of k elements.

answered Nov 11, 2011 at 15:04

JoeG

13.2k1 gold badge40 silver badges64 bronze badges

1 Comment

Ian McGrath Over a year ago

Thanks. Understod, what on earth was I thinking?

Blindy · Accepted Answer · 2011-11-11 15:05:32Z

1

That's O(n^2), the outer while goes from k down to 1 (possibly stopping earlier for specific data, but we're talking worst case here), and the inner for goes from 0 to i (which in turn goes up to k), so multiplied they're k^2 in the worst case.

If you care about the best case, that's O(n) because the outer while loop only executes once then gets aborted.

answered Nov 11, 2011 at 15:05

Blindy

67.9k10 gold badges96 silver badges140 bronze badges

Collectives™ on Stack Overflow

Time complexity of this function

3 Answers 3

Comments

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Related