GATE CS 2026 Set 1 Q51 — Asymptotic Worst Case Time and Space Complexity

To find the smallest positive integer $n$ for which $\text{foo}(n) = 5$, let us analyze the behavior of both recursive functions.

1. Behavior of bar(n):

• $\text{bar}(1) = 0$
• For $n > 1$, $\text{bar}(n) = 1 + \text{bar}(\lfloor n/2 \rfloor)$

This recurrence computes the floor of the base-2 logarithm: $\text{bar}(n) = \lfloor \log_2 n \rfloor$.

2. Behavior of foo(n):

• $\text{foo}(1) = 1$
• For $n > 1$, $\text{foo}(n) = 1 + \text{foo}(\text{bar}(n))$

3. Working Backwards to Minimize $n$:

Let $n_k$ be the smallest positive integer such that $\text{foo}(n_k) = k$.

• For $k = 1$: The smallest value is $n_1 = 1$.
• For $k = 2$: We need $\text{foo}(\text{bar}(n_2)) = 1$. To minimize $n_2$, we need the smallest $\text{bar}(n_2) = n_1 = 1$.
  $\lfloor \log_2 n_2 \rfloor = 1 \implies$ smallest $n_2 = 2^1 = 2$.
• For $k = 3$: We need $\text{foo}(\text{bar}(n_3)) = 2$. To minimize $n_3$, we need the smallest $\text{bar}(n_3) = n_2 = 2$.
  $\lfloor \log_2 n_3 \rfloor = 2 \implies$ smallest $n_3 = 2^2 = 4$.
• For $k = 4$: We need $\text{foo}(\text{bar}(n_4)) = 3$. To minimize $n_4$, we need the smallest $\text{bar}(n_4) = n_3 = 4$.
  $\lfloor \log_2 n_4 \rfloor = 4 \implies$ smallest $n_4 = 2^4 = 16$.
• For $k = 5$: We need $\text{foo}(\text{bar}(n_5)) = 4$. To minimize $n_5$, we need the smallest $\text{bar}(n_5) = n_4 = 16$.
  $\lfloor \log_2 n_5 \rfloor = 16 \implies$ smallest $n_5 = 2^{16} = 65536$.

Thus, the smallest positive integer $n$ for which $\text{foo}(n)$ returns $5$ is $65536$.