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)\]