Analysis of dependent double for
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.