505 views
0 votes
0 votes
We have for Counting Sort, O(n+k), for a simple uniform hashing, search operation of O(1+alpha) etc. What is the meaning when we say n + k? Is it that counting sort will depend on either n or k? Because there are separate loops in counting sort running on O(n) and O(k) separately. What does O(n + k) mean? What kind of algorithms have this summation for their order, generally?

1 Answer

0 votes
0 votes
CountingSort(A)
  A[]-- Initial Array to Sort
  Complexity: O(k)
  for i = 0 to k do
  c[i] = 0

  Storing Count of each element
  Complexity: O(n)
  for j = 0 to n do
  c[A[j]] = c[A[j]] + 1

   Change C[i] such that it contains actual
  position of these elements in output array
  Complexity: O(k)
  for i = 1 to k do
  c[i] = c[i] + c[i-1] 
  Build Output array from C[i]
  Complexity: O(n)
  for j = n-1 downto 0 do
  B[ c[A[j]]-1 ] = A[j]
  c[A[j]] = c[A[j]] - 1
end func

Because the algorithm uses only simple for loops, without recursion or subroutine calls, it is straightforward to analyze. The initialization of the count array, and the second for loop which performs a prefix sum on the count array, each iterate at most k + 1 times and therefore take O(k) time. The other two for loops, and the initialization of the output array, each take O(n) time. Therefore, the time for the whole algorithm is the sum of the times for these steps, O(n + k).

Because it uses arrays of length k + 1 and n, the total space usage of the algorithm is also O(n + k).

his algorithm, the initialization of the count array and the loop which performs a prefix sum on the count array takes O(k) time. And other two loops for initialization of the output array takes O(n) time. Therefore, the total time complexity for the algorithm is : O(k)+ O(n)+ O(k)+ O(n)= O(n+k).

Worst Case Time complexity: O (n+k)
Average Case Time complexity: O(n+k)
Best Case Time complexity: O(n+k)
Space Complexity: O(k)
Data Structure: Array
Sorting In Place: No
Stable: Yes

Related questions

0 votes
0 votes
1 answer
3