CODEWITHSUNDEEP
calgorithmtime-complexity
Ian McGrath
Ian McGrath

Reputation: 1012

Time complexity of this function

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.

Upvotes: 2

Views: 160

Answers (3)

Blindy
Blindy

Reputation: 67382

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.

Upvotes: 1

Werner Henze
Werner Henze

Reputation: 16726

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.

Upvotes: 2

JoeG
JoeG

Reputation: 13182

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.

Upvotes: 2

Related Questions