sortingtime-complexitycounting-sort

Why is the time complexity of counting sort O(n+k) instead of O(2*n)?


In counting sort we know that O(n+k) is the time compelxity where 'n' is the number of elements and 'k' is the range of elements given such as 1-100. Now look at the code below for counting sort:

void counting_sort(vector<int> & nums){
     //given nums[i] is between 1 and 5
     int arr[6];
     for (int i=0;i<nums.size();i++){
          arr[i+1]++;
     }
     // we have basically stored the frequency of values now in arr with O(n) time complexity
     for (int i=0;i<=5;i++){ // 5 here is just for example, in code it should be the largest value in nums array
          while (arr[i]>0){nums[i]=arr[i]; arr[i]--;}
     }
     //now we have stored the values in the sorted order in O(k) time complexity
     //total time complexity: O(n+k)
     
     return;
}

Now, my question is since we have to iterate over all the values in the second for loop with a while loop, shouldn't the time complexity of that loop be O(n)? Since we iterate over all the number of elements regardless of the for loop only going for 1 to k value (while loop to iterate over the frequency of numbers).

Hence, shouldn't the time complexity of countign sort be O(n+n)=O(2*n)=O(n) instead of O(n+k), where range is k? (Since the range is useless due to the while loop increasing the run time to n elements anyway)


Solution

  • You make two different loops the first on your elements (n) and the second on your range (k)

    n and k may be different so you have to consider them as two different variables.

    So the time complexity is:

    O(n) + O(k) = O(n+k)

    only if k is equal to n or less the complexity will be:

    O(n) + O(n) = O(n)

    If k is greater than n the complexity will be:

    O(n) + O(k) = O(k)

    We don't know which is bigger so we keep the two variable separated

    O(n) + O(k) = O(n+k)