# Is $n \log n$ in $O(n^{1.46-\varepsilon})$?

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)?

• Is the $-\varepsilon$ in the exponent? If not, then $\mathcal{O}(n^{1,46} - \varepsilon)$ is the same as $\mathcal{O}(n^{1,46})$. – Nathaniel Feb 21 at 12:44
• it is in the exponent – Diana Feb 21 at 12:48
• @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? – Diana Feb 21 at 13:48
• 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$. – Steven Feb 21 at 13:54

## 3 Answers

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.

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.

• What's the difference between this and my answers with the minus given? – zkutch Feb 21 at 13:01

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

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