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)
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)