GATE CS 2020 Q.12 (CS Q.2): Asymptotic Analysis and Time/Space Complexity

For parameters $a$ and $b$ , both of which are $\omega(1)$ , $T(n) = T(n^{1/a}) + 1$ , and $T(b) = 1$ . Then $T(n)$ is

$\Theta(\log_a \log_b n)$

$\Theta(\log_b n)$

$\Theta(\log_b \log_a n)$

$\Theta(\log_a n)$

Official answer and solution

Official answer: A
From: Official GATE 2020 answer key

Solution

Use repeated substitution or change of variables via iterated logarithms to solve the recurrence.

We are given the recurrence $T(n) = T(n^{1/a}) + 1$ with base condition $T(b) = 1$ , where $a, b = \omega(1)$ .

Take the logarithm to base $b$ on both sides of the argument. Let $n = b^{a^k}$ . Then:

\log_b n = a^k \implies \log_a(\log_b n) = k

In each step of the recurrence, $n$ is replaced by $n^{1/a}$ :

\log_b(n^{1/a}) = \frac{1}{a} \log_b n = \frac{a^k}{a} = a^{k-1}

Thus, the power $k$ decreases by 1 in each recursive step. The base case is reached when $n = b$ , which corresponds to $\log_b n = 1 = a^0$ , so $k = 0$ .

The number of steps required to reach the base case is $k$ . Since each step contributes $+1$ , we have:

T(n) = k + 1 = \Theta(k) = \Theta(\log_a \log_b n)

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 12 of 65, printed as CS Q.2
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source