$O(n)$ of $n/2^n$

Question

I have this program fragment where I am aware that first two for loops have a time complexity of n for both. However I am unsure as to how to determine the time complexity of the last for loop, for k = 1 to n/(2^j). I know that it could be interpreted as 1 to n/(2^n) but I do not know how that would look when you do a summation to find the overall time complexity.

How do I calculate the time complexity of this program?

sum = 0
for i = 0 to n-1
   for j = 0 to i 
      for k = 1 to n/(2^j)  
         sum ++

Answer 1

Calculate the sum as follows

$$ \sum_{i=0}^{n-1} \sum_{j=1}^i \sum_{k=1}^{n/2^j}1 = \sum_{i=0}^{n-1} \sum_{j=1}^i \frac{n}{2^j} = n \sum_{i=0}^{n-1} \sum_{j=1}^i \frac{1}{2^j}$$

using geometric progression this is equal to

$$ \sum_{i=0}^{n-1} 2\left(1 - \frac{1}{2^{i+1}}\right) = 2n^2 - 2n \sum_{i=0}^{n-1} \frac{1}{2^{i+1}} = 2n^2 - 4n\left(1 - \frac{1}{2^n}\right)$$ Thus,asymptotically, the first term dominates, and the complexity is $\Theta(n^2)$.