Solve the recurrence \(T(n) = 3T(\sqrt n) + \log n\). by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

Note: I don’t why suddenly \(\log\) is used in this problem statement, whereas till now everywhere \(\lg\) was used. I’m assuming in this context, \(\log\) still means \(\log_2 = \lg\).

Let us assume \(n = 2^m\), \(m = \lg n\).

Hence, the recurrence takes the form

\(T(2^m) = 3T(2^{m/2}) + m\).

Now, assuming \(S(m) = T(2^m)\), the recurrence takes the form

\(S(m) = 3S(m/2) + m\).

Let’s assume, \(S(m) \le cm^{\lg 3}\), for all \(m \ge m_0\), where \(c\) and \(m_0\) are some positive constants.

\[\begin {aligned}
S(m) & = 3S(m/2) + m \\
& \le 3c(m/2)^{\lg 3} + m \\
& = 3c \frac {m^{\lg 3}} {2^{\lg 3}} + m \\
& = cm^{\lg 3} + m
\end {aligned}\]

With this we cannot prove our assumption in it’s exact form.

So, let us modify our assumption by subtracting a lower-order term.