Asymptotic time complexity of recursive function (Theta)

Question

I have been asked to analyze the asymptotic time complexity of the following recursion function:

for-all k ≥ 1:
T(n) = n + T(n/2) + T(n/4) + T(n/8) + .... + T(n/2^k)

I was able to prove that:
T(n) = O(n⋅log n) and T(n) = Ω(n),
but I am looking for a tighter bound (Big Theta).

Answer 1

First of all:
I understand "for-all k >= 1" this way: for k = 1 to k = m where 2m-1 ≤ n ≤ 2m.
So basicly m = log₂(n) holds.

Have a look at my calculation:

T(n) = n + Σk=1,...,m T(n/2k)
     = n + T(n/2) + Σk=2,...,m T(n/2k)
     = n +  n/2 + 2⋅Σk=2,...,m T(n/2k)
     = ...
     = n + Σk=1,...,m k⋅n/2k
     = n + n⋅Σk=1,...,m k/2k
     = n + n⋅(2 - 2-mm - 21-m)
     ≤ n + 2⋅n
     = 3n

So T(n) is in Θ(n).

Notice:
You can also approximate Σk=1,...,m k/2k by the integral s(m) = ∫1m k/2k dk.
And here limm → ∞s(m) = 2 also holds.