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.

Let’s assume $$S(m) \le cm^{\lg 3} - bm$$.

\begin {aligned} S(m) & = 3S(m/2) + m \\ & \le 3(c(m/2)^{\lg 3} - b(m/2)) + m \\ & = 3c \frac {m^{\lg 3}} {2^{\lg 3}} - 3bm/2 + m \\ & = cm^{\lg 3} - bm - (b/2 - 1)m \\ & \le cm^{\lg 3} - bm \end {aligned}

The last step holds as long as $$(b/2 - 1)m$$ is positive.

If we set $$m_0 = 1$$, we need $$b \ge 2$$.

Changing our variable back to $$n$$, we have:

$T(n) = O(m^{\lg 3}) = O((\lg n)^{\lg 3}) = O(\lg^{\lg 3} n)$