prove logarithmic function is big oh of non logarithmic function

Question

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.

Answer 1

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

Answer 2

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