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.

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