1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – TMM May 27 '13 at 20:57
  • $\begingroup$ 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)$. $\endgroup$ – TMM May 27 '13 at 21:01
  • $\begingroup$ 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 $\endgroup$ – stackuser May 27 '13 at 21:19
  • $\begingroup$ 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.) $\endgroup$ – Mario Carneiro May 27 '13 at 21:24
  • $\begingroup$ 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. $\endgroup$ – stackuser May 27 '13 at 21:45
4
$\begingroup$

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}})} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks, not sure if you saw the comments above, but it seems to me that you didn't just disregard the constant log bases and let m = lg n. i'm trying to understand why. $\endgroup$ – stackuser May 28 '13 at 2:37
  • $\begingroup$ 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. $\endgroup$ – Adriano May 28 '13 at 4:31
  • $\begingroup$ brilliant. good explanation too. the only thing i don't see is what is happening with the base 'a' of the log. i'm trying to understand why that can be left as a variable. in the master theorem, it seems like in this case a=1, so i'm not sure why you don't just write 1 instead of a. and if a=1 then why write it all, the entire log expression is just 1 (1 raised to any power is still 1). $\endgroup$ – stackuser May 28 '13 at 5:16
  • $\begingroup$ 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. $\endgroup$ – Adriano May 28 '13 at 5:31
  • $\begingroup$ 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)$. $\endgroup$ – stackuser May 28 '13 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.