GATE CS 2015 Set 1 Q31 — Asymptotic Worst Case Time and Space Complexity

To find the return value of the function fun1(n), let us analyze the behavior of each loop step-by-step:

1. Outer Loop:
   The outer loop for (i = 1; i < n; ++i) runs exactly $n - 1$ times.
2. First Inner Loop:
   Inside the outer loop, p is initialized to $0$. The loop for (j = n; j > 1; j = j/2) repeatedly divides $j$ (starting at $n$) by $2$ until $j \le 1$.
   The number of iterations is the number of times we can divide $n$ by $2$, which is approximately $\log_2 n$. Thus, after this loop terminates:
   $$p \approx \log_2 n$$
3. Second Inner Loop:
   The loop for (k = 1; k < p; k = k * 2) starts with $k = 1$ and doubles $k$ in each iteration until $k \ge p$.
   The number of iterations of this loop is approximately $\log_2 p$. Since q is incremented by $1$ in each iteration, the increment to q per outer loop iteration is:
   $$\log_2 p \approx \log_2(\log_2 n)$$

Total Value of q:
Since the outer loop runs $n - 1$ times, and each iteration increments q by $\log_2(\log_2 n)$ times, the final value of q returned is:
$$q \approx (n - 1) \times \log_2(\log_2 n) = \Theta(n \log(\log n))$$

Therefore, the return value is most closely approximated by $n \log(\log n)$.