Theta bound for runtime analysis of nested while loops

Question

I am trying to fully analyze the running time of $\texttt{nestedLoops}$ in terms of $n$ with a Theta bound.

The Java code I have is as follows:

public void nestedLoops(int n) {
 int i = 1;
 while (i < n) {
 int j = i;
 while (j > 1) {
 int k = 0;
 while (k < n) {
 k += 2;
 }
 j = j // 2
 }
 i *= 2
 }
}

I know that the innermost while loop has an obvious runtime of $\lceil \frac{n}{2} \rceil$. But I get stuck on the next while loops. I think the middle while loop has a runtime of $\lfloor \log_2\texttt{i} \rfloor$, but that is very confusing for me.

Any help would be taken with much gratitude.

• greybeard: Try writing out all the formulas in full. If not convinced, present them to others.

Answer 1

The innermost loop has running time $\Theta(n)$. The middle loop runs for $\Theta(\log i)$ iterations. If 2ドル^m < 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). $$