1
$\begingroup$

I am trying to figure out the solution of the recurrence relation $$T(n) = 5T(n/3) + n \log n$$ using the Master Method.

I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the part that $\frac{n \log n}{n^{1.46}}$ must be polynomially smaller. If something is polynomially smaller does it mean it can not be bounded either from below or from above (or both)?

$\endgroup$
4
  • $\begingroup$ Is the $-\varepsilon$ in the exponent? If not, then $\mathcal{O}(n^{1,46} - \varepsilon)$ is the same as $\mathcal{O}(n^{1,46})$. $\endgroup$ – Nathaniel Feb 21 at 12:44
  • $\begingroup$ it is in the exponent $\endgroup$ – Diana Feb 21 at 12:48
  • $\begingroup$ @Steven when I want to show that something is polynomially larger I find polynomials and bound the expression from below and above. Does it mean that in the case I want to show it is polynomially smaller I can not bound it from below by polynomial? $\endgroup$ – Diana Feb 21 at 13:48
  • $\begingroup$ If you want to show that $f(n)$ is polynomially larger than $g(n)$ you just need to find a lower bound to $f(n)$ of $\Omega( g(n) n^\varepsilon)$ for some $\varepsilon > 0$. No need to bound $f(n)$ from above. When you need to show that $f(n)$ is polynomially smaller than $g(n)$ you only need to bound $f(n)$ from above with some function in $O(g(n) n^{-\varepsilon})$, for some $\varepsilon > 0$. No need to bound $f(n)$ from below. By the way my previous comment was incorrect (I had calculated the wrong value for $\log_3 5$) but I was just making explicit that $\log_3 5 \neq 1.46$. $\endgroup$ – Steven Feb 21 at 13:54
2
$\begingroup$

When $f(n)$ is said to be polynomially smaller than $g(n)$ it just means that there is some constant $\varepsilon > 0$ such that $f(n) \in O(g(n) n^{-\varepsilon})$. This is not about being able to bound $f(n)$ from above and/or below but about the growth rate of $f(n)$ when compared to $g(n)$. In other words you want $\frac{g(n)}{f(n)}$ to grow at least as fast as some polynomial/root of $n$.

In your particular case, $n \log n$ is indeed polynomially smaller than $n^{1.46}$, and this follow from the fact that $n \log n \in O(n^\alpha)$ for any $\alpha >1$.

A a concrete choice of $\varepsilon$, you can pick $\varepsilon=0.1$ yielding $n \log n \in O(n^{1.46-0.1}) = O(n^{1.36})$.

To see this you can consider the limit: $$ \lim_{n \to \infty} \frac{n \log n}{n^{1.36}} = \lim_{n \to \infty} \frac{\log n}{n^{0.36}} = \lim_{n \to \infty} \frac{1}{0.36 \cdot n^{0.36}} = 0, $$ where we used L'Hôpital's rule.

In the above, the choice $\varepsilon = 0.1$ was just a convenient value that works, but any choice of $\varepsilon \in (0, 0.46)$ suffices.

$\endgroup$
0
$\begingroup$

It is well known, that for any fixed number $a>0$ we have $\log(n)=O(n^a)$.

Then, for a small enough epsilon, that is for $\epsilon<0.46$ we can define $a=0.46-\epsilon>0$. Therefore, $log(n)=O(n^{0.46-\epsilon})$. Multiply by $n$ both sides and you get the solution.


In fact, $\log(n)=o(n^a)$, and therefore not only $n\log(n)=O(n^{1.46-\epsilon})$, but also $n\log(n)=o(n^{1.46-\epsilon})$ which means that $n\log(n)$ grows substantually slower than $n^{1.46-\epsilon}$.

Therefore, $n\log(n)$ cannot be bounded from below by $n^{1.46-\epsilon}$ but can be bounded from above.

$\endgroup$
1
  • $\begingroup$ What's the difference between this and my answers with the minus given? $\endgroup$ – zkutch Feb 21 at 13:01
-1
$\begingroup$

Answering title: $n\lg n = O(n^{1,46 - \varepsilon})$, when $\varepsilon \lt 0.46$.

$\endgroup$
3
  • $\begingroup$ Explicit and well-founded criticism is welcome, especially when what is written is true. $\endgroup$ – zkutch Feb 21 at 12:59
  • $\begingroup$ The OP also wanted to know why. Not only if its true or false. $\endgroup$ – nir shahar Feb 21 at 13:02
  • $\begingroup$ Transferring a term over an inequality sign is not an explanation, as well as passing one's own opinion as someone else's. $\endgroup$ – zkutch Feb 21 at 13:06

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.