What is the asymptotic complexity of the following code snippet?
The second loop runs in $O(i)$. The first loop goes over the powers $2^{2^0}, 2^{2^1}, 2^{2^2}, \ldots$, until reaching $n$. So the overall running time is
$$
O(2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m}),
$$
where $m$ is the maximal integer such that $2^{2^m} &lt; n$. We can bound
$$
2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m} \leq 2^1 + 2^2 + 2^3 + \cdots + 2^{2^m} \leq 2^{2^m+1} &lt; 2n.
$$
Therefore the overall running time is $O(n)$.

In fact, the same analysis gives the optimal bound $\Theta(2^{2^{\lfloor \log_2 \log_2 (n-1) \rfloor}})$, with a bit more work.