سوال ۵۸ کنکور ارشد مهندسی کامپیوتر ۱۴۰۵

Use the standard variable-substitution trick for square-root recurrences. Let $n = 2^{m}$, so that $m = \log n$ and $\sqrt{n} = 2^{m/2}$. Define

$S(m) = T\left(2^{m}\right).$

The recurrence $T(n) = 2T(\sqrt{n}) + \log n$ turns into

$S(m) = 2\,S\!\left(\tfrac{m}{2}\right) + m.$

This is exactly the merge-sort recurrence. Applying the Master theorem with $a = 2$, $b = 2$: $\log_b a = \log_2 2 = 1$ and $f(m) = m = \Theta(m^{1}) = \Theta\!\left(m^{\log_b a}\right)$, so we are in case 2:

$S(m) = \Theta(m \log m).$

Now undo the substitution with $m = \log n$ (hence $\log m = \log\log n$):

$T(n) = S(\log n) = \Theta\!\left(\log n \cdot \log\log n\right).$

Therefore $T(n) = O(\log n \log\log n)$, which is option 1. The floor $\lfloor\cdot\rfloor$ does not change the asymptotics.

Exam trick: For any recurrence of the form $T(n) = a\,T(\sqrt{n}) + f(n)$, substitute $n = 2^{m}$ to collapse the square root into a halving argument, solve the resulting standard recurrence, then translate every $m$ back to $\log n$.