# Understanding how to assign complexity to functions

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.

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?

• 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. Feb 18 at 18:06