3
$\begingroup$

$$T (n) = 3T (n/5) + \log^2 n$$

i am trying to solve this recurrence i have been told that it is master methods case 1 but how do i compare $\log^2n$ with $n^ {\log_5 3}$

$\endgroup$
1
  • $\begingroup$ i mean how can i decide weather $log^2n$ = $O(n^{log_5 3})$ or not $\endgroup$ Dec 28, 2010 at 14:50

4 Answers 4

4
$\begingroup$

A rule of thumb is that polynomial functions always grow faster than logarithmic functions. E.g. this lecture. So your polynomial function asymptotically dominates your log function, giving you case 1.

If you want to know why powers grow faster than logs, you can put the functions in a ratio and then evaluate $\lim_{n\to \infty} \frac{f(n)}{g(n)}$.

$\endgroup$
6
  • $\begingroup$ polynomials grow faster than logs agreed, but in this case it's the square of the log function how to go about that ? $\endgroup$ Dec 28, 2010 at 15:46
  • $\begingroup$ am i doing something incorrect here ? $\endgroup$ Dec 28, 2010 at 15:52
  • 1
    $\begingroup$ Polys grow faster than logs, no matter what power you raise the logs to. You can take the limit of the ratio to prove this, or look at Trevor's answer below where he works through the math. $\endgroup$
    – dsolimano
    Dec 28, 2010 at 16:00
  • 2
    $\begingroup$ @Bunny Rabbit: Consider $n=e^x$ and the fact that $e^{\varepsilon x}$ grows faster than $x^m$, for any $\varepsilon>0$ (small as you wish) and $m>0$ (large as you wish). $\endgroup$
    – Shai Covo
    Dec 28, 2010 at 16:04
  • $\begingroup$ @dsolimano Thanks a lot for your comment it helped a lot. $\endgroup$ Dec 28, 2010 at 19:55
3
$\begingroup$

This comment below makes explicit what the first answer already said, and hopefully removes the confusion regarding polylogs that seems to persist in the OP's mind.

To see why, consider $$\lim_{n \to \infty} \frac{(\log n)^k}{n^\epsilon}$$ for any positive $\epsilon$ and any positive integer $k$ (integrality is not really necessary, but suffices for our purposes).

We have $$\lim_{n \to \infty} \frac{(\log n)^k}{n^\epsilon} = \lim_{n \to \infty} \underbrace{\frac{\log n}{n^{\epsilon/k}}\cdots \frac{\log n}{n^{\epsilon/k}}}_{k-\mathrm{times}}.$$

Thus, it all boils down to proving that $$\lim_{n \to \infty} \frac{\log n}{n^\gamma} = 0,$$ where $\gamma > 0$, and we already know how to prove this.

So, I hope this provides the clarification the OP sought.

$\endgroup$
2
$\begingroup$

So we want to show that $T(n) = \Theta(n^{\log_{b}a})$ and $f(n) = O(n^{\log_{b}(a)-\epsilon})$. So $a=3, b=5, f(n) = \log^{2} n$, and $\log_{5} 3 = 0.6826$. So we check the following:

  • $f(n) = \log^{2} n = O(n^{0.6826- \epsilon})$. So choose any $\epsilon >0$. In other words, $\log^{2} n \in o(n^{0.6826- \epsilon})$. Note the derivative of $(\log n)^2 = \frac{2 \log n}{n}$ and the derivative of $n^{0.6826}$ is $\frac{0.6826}{n^{0.3174}}$.

The result follows.

$\endgroup$
1
  • $\begingroup$ but this is what my question was how do we arrive at the result that $n^{0.6826- \epsilon}$ asymptotically larger than $\log^{2} n$ $\endgroup$ Dec 28, 2010 at 15:50
1
$\begingroup$

There is another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and $T(1)=T(2)=T(3)=T(4)=1$ and for $n\ge 5$ $$T(n) = 3 T(\lfloor n/5 \rfloor) + \lfloor \log_5 n \rfloor^2.$$

Then we can unroll the recurrence to obtain the following exact formula for $n\ge 5$ $$T(n) = 3^{\lfloor \log_5 n \rfloor} + \sum_{j=0}^{\lfloor \log_5 n \rfloor -1} 3^j \times (\lfloor \log_5 n \rfloor - j)^2.$$ Note that this is independent of the actual digits of $n.$

This simplifies to $$\frac{5}{2} 3^{\lfloor \log_5 n \rfloor} - \frac{1}{2} \lfloor \log_5 n \rfloor^2 - \frac{3}{2} \lfloor \log_5 n \rfloor - \frac{3}{2}.$$

Now the first term is obviously the dominant one asymptotically, so that we get the following answer for the complexity of the recurrence:

$$T(n)\in\Theta\left(3^{\lfloor \log_5 n \rfloor}\right) = \Theta\left(3^{\log_5 n}\right) = \Theta\left(5^{\log_5 3 \times \log_5 n}\right) = \Theta\left(n^{\log_5 3}\right).$$

This agrees with what the Master Theorem would say.

This MSE link has a series of similar calculations.

$\endgroup$

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.