I want to know more about the $O$-Notation, but can't seem to grasp the idea of it. It essentially formalizes the notation that 2 functions "grow at the same rate" or "one function grows faster than the other". So if $f(n)=1000n^2$, $g(n)=n^3$. When $n>1000$ $f(n)<g(n)$ so we say that $f(n)=O(g)=O(n^3)$.
Now let's consider $h(n)=3n^4+5n^3+7\log_2n$ and $y(n)=n\log_2n$. How do I show that $h(n)=3n^4+5n^3+7\log_2n$ and $y(n)∈O(n^2)$.
To show that $n \log_2 n = O(n^2)$, we want to show that there exists a constant $C$ such that, for $n$ sufficiently large (depending, at most, on $C$) $$ | n \log_2 n | < C n^2. $$ Noting that for $n>1$ we have $n \log_2 n >0$, we can dispense with the absolute values.
We can study the function $$ f(n) = \frac{n \log_2 n}{n^2} = \frac{\log_2 n}{n}. $$ It is not hard to show that $f(n)<1$ for all $n\ge 1$ . Hence, we have that $$ n \log_2 n < n^2$$ for $n>0$ and so $n \log_2 n = O(n^2)$.