There is some problem with your notation. The general organ should be:
T(n) = T(n/2^(i+1)) + sum from k=0 to i of 2^(n/2^k)
After this step, we let i = log(2, n) - 1
, so that T(n/2^(i+1)) = T(1)
.
Therefore, T(n) = T(1) + sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k)
.
Note that sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k)
is 2^n + 2^(n/2) + 2^(n/4) + ...
, which is smaller than 2^n + 2^(n-1) + 2^(n-2) + ...
. However, the latter stuff is 2^(n+1) - 1
. So the former stuff is something between 2^n
and 2^(n+1)
. Therefore, the sum is O(2^n)
.
Then T(n) = O(2^n)
.