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.

Answer 1

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.

Answer 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.

Answer 3

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.