# runtime of 2 dependent nested for loops [duplicate]

for (i=1; i<=n ;i=i*2){

for (j=1; j<=i ;j++){

basic_step;

}
}


Regarding the above nested loops, I can't seem to understand why is the following runtime analysis is correct (specifically the first equality), when $$k$$ is defined as $$\log i$$, meaning $$i=2^k$$. What is the process that one should come up with, in order to decide this setting and the sigmas' indices? While I do understand that the outer loop runs for $$\Theta(\log n)$$ times, I still can't grasp the setting of $$k$$. A clarification will be very much appreciated!

$$\sum_{k=0}^{\log n}\sum_{j=1}^{2^k}1$$

The value of $$i$$ at the $$k$$'th iteration (starting from zero) is $$i_k := 2^k$$. The inner loop runs $$i_k$$ times, for a total of $$i_0 + i_1 + \cdots + i_K$$, where $$K$$ is the largest number such that $$i_K \leq n$$, that is $$\lfloor \log_2 n \rfloor$$. Therefore the running time is $$\sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k = 2^{\lfloor \log_2 n \rfloor + 1} - 1 = \Theta(n).$$