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.

Let \(m = \lg n\). Then we have \(T(2^m) = 3T(2^{m/2}) + m\) and we can rename \(S(m) = T(2^m)\) to produce the new recurrence \(S(m) = 3S(m/2) + m\). We can use the master method on this recurrence and so we have \(a = 3\), \(b = 2\) and \(f(m) = m\).

Case 1 applies since \(f(m) = O(m^{\log_2 3 - \epsilon}) = O(m^{\log_2 2}) = O(m)\), and thus the solution to the recurrence is \(S(m) = \Theta(m^{\log_2 3}) = O(m^{\lg 3})\).

In order to show asymptotic tightnes, let’s confirm that \(S(m) = O(m^{\lg 3})\) by guessing that \(S(m) \leq cm^{\lg 3} - bm\). Substituting this into the recurrence yields

\[\begin{split} S(m) & \leq 3 \left( c \left( \frac{m}{2}\right)^{\lg 3} - b \frac{m}{2}\right) + m \\ & = 3 \left( \frac{cm^{\lg 3}}{2^{\lg 3}} - \frac{bm}{2} \right) + m \\ & = \frac{3cm^{\lg 3}}{3} - \frac{3bm}{2} + m \\ & = cm^{\lg 3} - \frac{3bm}{2} + m \\ & \leq cm^{\lg 3} - bm \\ \end{split}\]

Where the last step holds for \(b \geq 2\). Next, let’s confirm that \(S(m) = \Omega(m^{\lg 3})\) by guessing that \(S(m) \leq cm^{\lg 3}\). Substituting this into the recurrence yields

\[\begin{split} S(m) & \geq 3c \left( \frac{m}{2} \right)^{\lg 3} + m \\ & = 3c \frac{m^{\lg 3}}{3} + m \\ & = cm^{\lg 3} + m \\ & \geq cm^{\lg 3} \\ \end{split}\]

Where the last step trivially holds. The combination of \(S(m) = O(m^{\lg 3})\) and \(S(m) = \Omega(m^{\lg 3})\) means that our solution is asymptotically tight, or in other words \(S(m) = \Theta(m^{\lg 3})\).

Lastly, changing back from \(S(m)\) to \(T(n)\) we obtain

\[T(n) = T(2^m) = S(m) = \Theta(m^{\lg 3}) = \Theta(\lg^{\lg 3} n)\]