Analysis of dependent double for Here is the algorithm:

int sum = 0
for (int i = 2N; i &gt; 0; i = i / 4) {
  for (int j = 0; j &lt; i; j+=2) {
    sum++
  }
}


I figured this would be linearithmic, but it's just linear. I would appreciate seeing a formalized summation and not a qualitative explanation. I have tried doing this but I fail to get linear runtime.
The number of iterations is:
$$T = \frac{2N}{2} + \frac{2N}{2 * 4} + \cdots + 1$$

The number of elements in the above formula is $\log_4(2N)$. After simplification, we will have:

$$T = N(1 + \frac{1}{4} + \cdots + \frac{1}{4^{\log_4(N)}}) = \Theta(N)$$

As $1 + \frac{1}{4} + \cdots + \frac{1}{4^{\log_4(N)}} &lt; 2$ is a geometric series with step of $\frac{1}{4}$ in asymptotic sense.