made easy test series 2025

Question

Identify Correct Asymptotic Behviour.

Comments

main is using property of log : 4^log_3(logn) = logn ^(log_3 (4))
By solving recursion tree method i'm getting this :

T(n)=logn(logn)^log_3(4)  = logn^(1+log_3(4))  so basically T(n) = (logn )^(log_3 (4))
Or solve it by back substitution.

Answer 1

If you keep substituting the terms, the recurrence becomes:

\[
T(n) = \Theta\!\left( \log n \left(\frac{4}{3}\right)^{k} \right),
\]

where

\[
k = \log_{3}\!\left( \log_{2} n \right).
\]

So the final answer is:

\[
T(n) = \left( \log_{2} n \right)^{\log_{3} 4}.
\]