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

GATE CSE 2020 Q12: Solve T(n) = T(n^(1/a)) + 1 with T(b) = 1

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

Try it: multiple choice: exactly one correct option

Wrong answer costs 1/3 mark in GATE.

Show answer and explanation

Answer: A (official GATE 2020 final answer key)

Concept used: Count how many times $n$ can be replaced by its $a$ -th root before it reaches the base value $b$ .

First step: After $k$ steps the argument is $n^{1/a^k}$ ; set $n^{1/a^k} = b$ and solve for $k$ .

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key