Linear functions vs Linearithmic functions complexity

Question

Can we say Linear functions complexity is lower than Linearithmic functions? ie:

θ(4n) < θ(nlog(n)) for n >= 1

If so, How?

Answer 1

First, your notation with the Big-O symbol is not the most conventional; to denote that the time complexity of $4n$ grows slower than that of $n\log{n}$, we would use the Little-O symbol: $$4n \in o(n \log{n})$$ Proving this is quite trivial: since $$ \lim_{n \to \infty} \frac{4n}{n \log{n}} = \lim_{n \to \infty} \frac{4}{\log{n}} = 0 $$ by definition we have $4n \in o(n\log{n})$.