The GATE Grind

GATE 2020 CS – Question 12

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

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

  1. $\Theta(\log_a \log_b n)$
  2. $\Theta(\log_{ab} n)$
  3. $\Theta(\log_b \log_a n)$
  4. $\Theta(\log_2 \log_2 n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\Theta(\log_a \log_b n)$

Explanation

After $k$ steps the argument is $n^{1/a^k}$. Setting this equal to $b$ gives $a^k=\log_b n$, so $k=\log_a\log_b n$. Hence $T(n)=\Theta(\log_a\log_b n)$.