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)

CodePudding user response：

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)