GATE CS 2020 Q2 — Asymptotic Worst Case Time and Space Complexity

To solve the given recurrence relation, we can use the substitution method.

The recurrence is given by:
$$T(n) = T(n^{1/a}) + 1$$ with the base case $T(b) = 1$.

Let us assume $n = b^{a^k}$ for some integer $k \ge 0$. Taking the logarithm on both sides:

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

Now, let $S(k) = T(b^{a^k})$. Substituting this into the recurrence relation:

$$S(k) = S(k-1) + 1$$

The base case is when $k = 0$:

$$S(0) = T(b^{a^0}) = T(b) = 1$$

Solving the linear recurrence $S(k) = S(k-1) + 1$ with $S(0) = 1$ yields:

$$S(k) = k + 1$$

Substituting back $k = \log_a (\log_b n)$:

$$T(n) = \log_a (\log_b n) + 1$$

Therefore, the asymptotic complexity is:

$$T(n) = \Theta(\log_a \log_b n)$$