Theta bound for runtime analysis of nested while loops
The innermost loop has running time $\Theta(n)$. The middle loop runs for $\Theta(\log i)$ iterations. If $2^m &lt; n \leq 2^{m+1}$, this means that the total running time is proportional to
$$
n (\log 1 + \log 2 + \cdots + \log 2^m) = n \log 2(0 + 1 + \cdots + m) = \Theta(n m^2) = \Theta(n\log^2 n).
$$