Exercise 4.3.9

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

Let's go this way:

$$ \begin{aligned} T(n) & = 3T(\sqrt{n}) + \lg{n} & \text{rename } m = \lg{n} \\ T(2^m) & = 3T(2^{m/2}) + m \\ S(m) & = 3S(m/2) + m \end{aligned} $$

Now we guess $S(m) \le cm^{\lg{3}} + dm$:

$$ \begin{aligned} S(m) & \le 3\Big(c(m/2)^{\lg{3}} + d(m/2)\Big) + m \\ & \le cm^{\lg{3}} + (\frac{3}{2}d + 1)m & (d \le -2) \\ & \le cm^{\lg{3}} + dm \end{aligned} $$

Then we guess $S(m) \ge cm^{\lg{3}} + dm$:

$$ \begin{aligned} S(m) & \ge 3\Big(c(m/2)^{\lg{3}} + d(m/2)\Big) + m \\ & \ge cm^{\lg{3}} + (\frac{3}{2}d + 1)m & (d \ge -2) \\ & \ge cm^{\lg{3}} + dm \end{aligned} $$

Thus:

$$ \begin{aligned} S(m) & = \Theta(m^{\lg{3}}) \\ T(n) & = \Theta(\lg^{\lg{3}}{n}) \end{aligned} $$