Gate CS 2020 | Question - 2 | Algorithms

$T\left(n\right)=\left\{\begin{array}{l}T\left(n\right) =T\left(n^{1/a}\right) if n \ne b\\ T\left(n\right)=1 if n = b\end{array}\right.$

Given: T(n) = T(n^1/a) + 1

T(n^1/a) = T(n^1/a2) + 1

T(n^1/a2) = T(n^1/a3) + 1

From Above Equations,
T(n) = T(n^1/a3) + 3

After k iteration,

T(n) = T(n^1/ak) + k

When, n^1/ak = b  ---- (1)

Apply log both sides on equation (1)

$\frac{1}{a^k}\log n=\log b$

$\frac{1}{a^k}=\frac{\log b}{\log n}$

$a^k=\frac{\log n}{\log b}$

Apply log again on both sides with base a,

k = log_alog_bn

a and b are some functions of n and are not constant. So a and b can’t be replaced with 2. So Option D is rejected and the correct answer is Option A.