I'm having trouble understanding how to assign complexity to functions. As an example, let's take the following pseudo code of the COUNTING-SORT algorithm, taken from the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.

enter image description here

In the book the complexity is assigned in the following way:

How much time does counting sort require? The for loop of lines 2–3 takes time Θ(k), the for loop of lines 4–5 takes time Θ(n), the for loop of lines 7–8 takes time Θ(k), and the for loop of lines 10–12 takes time Θ(n). Thus, the overall time is Θ(k+n). In practice, we usually use counting sort when we have k=O(n), in which case the running time is Θ(n).

Why the overall time is Θ(k+n) and not Θ(k)+Θ(n)? or is it the same thing?

  • $\begingroup$ Strictly speaking, the notation $\Theta(k)+\Theta(n)$ is not defined. You do not perform arithmetic with $\Theta$ as if it was a quantity. In fact it denotes a family of functions. $\Theta(k+n)$ is safe. $\endgroup$ Feb 18 at 18:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.