# Master Theorem change of variables with root other than 2

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$.

• You could substitute $k = \log_3(m)$ to get an equation of the form $R(k) = 12 R(k-1) + \dots$, which leaves you with a geometric series. – TMM May 27 '13 at 20:57
• Note that $\log_a(x) = \log_b(x) / \log_b(a)$, so if $b$ and $a$ are constant (say $2$ and $3$), $\Theta(\log_a x) \equiv \Theta(\log_b x)$. – TMM May 27 '13 at 21:01
• sorry not quite following you. i was expecting the next step to be something like $$S(m) = \Theta(m^{2} \log_3 m)$$ so that 1 of the 3 cases is found. i'm not sure how the geometric series would fit in. i can somewhat see how a change of base would be helpful but i'm also not seeing exactly how it works in this case. i'm learning this as i go, thanks for your patience – stackuser May 27 '13 at 21:19
• The base on a log is usually ignored in big-$O$ notation because $\log_a x$ and $\log_b x$ are related by a multiplicative constant for any bases $a$ and $b$, and these are exactly what the big-$O$ notation ignores. (This is what TMM's second comment is about.) – Mario Carneiro May 27 '13 at 21:24
• ok so if i understand you correctly, then what you're saying is that we use $\Theta(m^{2} \log m)$ here. or do we just use $\Theta(m \log m)$ since the constants are ignored. thanks for clarifying the above comment, i now understand what that was about. the only thing i'm not sure about is whether this is $m$ or $m^{2}$ as i noted above. – stackuser May 27 '13 at 21:45

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}})}$$
• Notice that $(3n)^2 = 9n^2 = \Theta(n^2)$, so we can disregard the $3$. However, we can NOT say that $2^{3n}=\Theta(2^n)$ because in fact $2^{3n}=(2^3)^n=8^n=\Theta(8^n)$. In general, constants can be dropped if it is in the base, but not if it is in the exponent. – Adriano May 28 '13 at 4:31
• Hmm, I'm not sure what you mean. In my solution (when solving the recurrence for $S(m)$), I had $a=12, b=3$ and I had to compare $(\log{3})^2{m}^2$ with $m^{\log_b{a}}$. The base of the log is $b=3$, not $a$. The size of the font for the subscript can make it a bit hard to read. – Adriano May 28 '13 at 5:31
• ok i think i see. you have $b=3$ from $S(m/3)$ so that 3 is your base. the change of variables is really new for me (so is master theorem), so i sometimes look at the $T(n)$ instead of the $S(m)$. – stackuser May 28 '13 at 5:54