0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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$
    – Yves Daoust
    Feb 18 at 18:06

0

Reset to default

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.