A student came up with following observation and interesting question:
To recall Θ(1)+Θ(1)=Θ(max(1,1))=Θ(1).
The student asked, if we do this n times, do we get ∑_{i=1..n} Θ(1)=Θ(max(1, .. ,1))=Θ(1)?
The answer is 2-fold, depending on whether n is a constant or the size of the input.
In the question, n is the input-size, in which case the answer is NO.
I explain shortly why ∑_{i=1..n} Θ(1) = Θ(n).
The rule Θ(f_1)+Θ(f_2)=Θ(max(f_1,f_2))
is correct for a constant number of summands (here 2 summands).
For two terms, we use max(f_1,f_2) ≤ f_1+f_2 ≤ 2*max(f_1,f_2),
and the factor 2 is "absorbed" by Θ.
For m summands f_1,..f_m, the correct bound is then
max_i f_i ≤ ∑_{i=1..m} f_i ≤ m*max_i f_i
If now m is equal to the input size n, then m is not a constant.
In particular, if each summand f_i = Θ(1), then
∑_{i=1..n} Θ(1)= n Θ(1) = Θ(n) ≠ Θ(1)
In short: the sum of a constant number of Θ(1)-terms is still in Θ(1),
but n terms of size Θ(1) sum to Θ(n)