# Theta bound for runtime analysis of nested while loops

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.

• Try writing out all the formulas in full. If not convinced, present them to others. Apr 5 at 7:10

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).$$