# prove logarithmic function is big oh of non logarithmic function

I am having trouble knowing how to find out whether a given logarithmic function, |f(x)|, is an element of the set of all functions less than or equal to C * |g(x)| where g(x) is a non-logarithmic function for some C and k such that x > k.

For example:

Say I am trying to prove that:

|N log N| <= C * |N^3| for some C and k where x > k

A way to establish whether this statement is true would be to solve for C. If C is not a function of N, then the statement holds true. To better be able to divide f(x) by g(x) to get a useful value would be to increase f(x). If f'(x) is still less than C * g(x) then we can still divide it by g(x) to get a useful value for C that can help prove whether the initial statement is true.

My struggle is what do I do if I am comparing a logarithmic function to a non-logarithmic function? It seems like it would be extremely difficult to increase N log N in to something that can be divided by N^3. Is there a way to do this? I have been doing research on logarithms and have not, so far, been able to find a way to do this.

You could use limits to prove this, or you could prove it algebraically as follows:

For all $$n \ge 1$$, $$n \le e^n$$ $$\log n \le \log e^n$$ $$\log n \le n$$ $$n \cdot \log n \le n \cdot n^2$$ $$n \log n \le n^3$$ Hence, $$n \log n = O(n^3)$$

• I understand everything except the second to last step where you multiply log n by n and n by n^2. Why are you able to do that? – Darien Springer Oct 17 '19 at 21:40
• is it because it is not an equality statement but an inequality statement? – Darien Springer Oct 17 '19 at 21:54
• Exactly. The statement is an inequality, so there is no requirement to multiply both sides by the same quantity - as long as the inequality still holds. In this case $n \le n^2$ for $n \ge 1$, so if $a \le b$, then $an \le bn^2$. This sort of technique is used all the time with inequalities. – RyRy the Fly Guy Oct 17 '19 at 22:25
• If you are satisfied with your answer, then please click the green check to close the post. Thanks! – RyRy the Fly Guy Oct 17 '19 at 22:28
• Also how does log e^n = n? Wouldn't it equal whatever exponent value would make e = n? – Darien Springer Oct 17 '19 at 22:50

$$\lim_{n\to\infty}\frac{n\log{(n)}}{n^3}=0\implies n\log{n}=o(n^3)$$ i.e. the statement is true $$\forall \,C\gt0$$ as long as $$k$$ is suitably chosen.

• Yes but can I prove this more algebraically? In this case I have to just assume that as n approaches infinity that n^3, for some value of C and k when x > k, will grow faster than n log n forever after that point. Because if I just prove that one function will reach a point where it grows faster than the other using the assumption that one grows faster than the other, then haven't I used circular reasoning? Or am I misunderstanding your reasoning here? – Darien Springer Oct 17 '19 at 20:44
• Maybe you could use this question? – Peter Foreman Oct 17 '19 at 20:47