Master Theorem change of variables with root other than 2

5.6k Views Asked by At

I'm working on this:

$$T(n) = 12T(n^{1/3}) + \log(n)^{2}$$

Using change of variables, and substituting $m = \log n$, I get as far as:

$$S(m) = 12S(m/3) + m^{2}$$

I see how a square root would work but with a cube root I'm not sure that $\Theta(m \log m)$ makes sense since the convention seems to be that this means $\log_2 n$ and I'm not seeing how that accounts for a base $3$ $\log$.

1

There are 1 best solutions below

5
On BEST ANSWER

Let $n=3^m$ (that is, let $m=\log_3n$). Then by a change of variables, we have: $$ T(3^m) = 12T((3^m)^{1/3}) + (\log(3^m))^{2} = 12T(3^{m/3}) + (m\log3)^{2} = 12T(3^{m/3}) + (\log3)^{2}m^2 $$ Renaming $S(m)=T(3^m)$ yields: $\boxed{S(m)=12S(m/3)+(\log3)^{2}m^2}$

Since $\log_3{12}>\log_3{9}=2$, it follows that $(\log3)^{2}m^2=O(n^{\log_3{12}-\epsilon})$ if $0<\epsilon\le\log_3{12}-2$. Thus, by Case 1 of the Master Theorem, we have $\boxed{S(m)=\Theta(m^{\log_3{12}})}$. Changing variables back to the original recurrence yields: $$ T(n)=T(3^m)=S(m)=\Theta(m^{\log_3{12}})=\Theta((\log_3n)^{\log_3{12}})=\boxed{\Theta((\log n)^{\log_3{12}})} $$ Using the identity $x^{\log_b{y}}=y^{\log_b{x}}$, we can alternatively write this as: $$ T(n)=\boxed{\Theta(12^{\log_3{\log n}})} $$