Intuitively, the idea is that the "order" of a function is that of its highest-order term. In $x^4 + x^2 + 1$, you can usually ignore everything except the $x^4$, and say that it is $O(x^4)$ and not $O(x^d)$ for any smaller $d < 4$. Similarly $x^3 + 1$ is of the order of $x^3$, and in general a polynomial of degree $d$ is of the order of $x^d$.
So in your first function $f(x) = f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$, the numerator is of order $x^4$ and the denominator is of order $x^3$, so the fraction $f(x)$ is of order $\frac{x^4}{x^3} = x$.
That's the idea of what's really going on, but to prove it formally, you can do the division: write $f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1} = x + \frac{x^2 - x + 1}{x^3 + 1}$, and observe that the remainder term $\frac{x^2 - x + 1}{x^3 + 1} = \frac{1}{x+1} \to 0$ as $x \to \infty$, so $f(x) = O(x)$ and not $O(x^{1 - \epsilon})$ for any $\epsilon > 0$.
You don't even have to do the division completely: just get rid of the $x^3$ terms from both numerator and denominator. Observe that
$$f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}
= \frac{(x^4 + x^2 +1)/x^3}{(x^3 + 1)/x^3}
= \frac{x + \frac{1}{x} + \frac{1}{x^3}}{1 + \frac{1}{x^3}}$$
and you can prove directly from this that $f(x) = O(x)$.
Similarly, for the second function, $f(x) = \frac {x^4 + 5 \log x}{x^4 + 1}$, both numerator and denominator are of the same order $x^4$, so you should expect the fraction to be $O(1)$. You can prove it by writing
$$f(x)
= \frac {x^4 + 5 \log x}{x^4 + 1}
= \frac {(x^4 + 5 \log x)/x^4}{(x^4 + 1)/x^4}
= \frac{1 + \frac{5 \log x}{x^4}}{1 + \frac{1}{x^4}}
$$
and proving from there that $f(x) = O(1) = O(x^0)$.
(E.g. you can show that, for $c_1 = \frac12$ and $c_2 = 2$ (say) and sufficiently large $x$, we have $c_1 \le f(x) \le c_2$, since $f(x) \ge \frac{1}{1 +\frac1{x^4}} \ge \frac{1}{2}$ when $x \ge 1$, and similarly $f(x) \le \frac{1 + \frac{5\log x}{x^4}}{1} \le 2$ when $\frac{5 \log x}{x^4} \le 1$, which again is true for sufficiently "large" $x$. Actually in this case any constants $c_1 < 1 < c_2$ will do, since $\lim_{x\to\infty} \frac{f(x)}{x} = 1$, but we don't need all this just to prove that $f(x) = O(1)$.)
To answer @sol4me If you know some better way then please share, i will be glad to know.
First, never trust a plot. You just saw it may hurt, so even if it can help, it's not a proof.
Then, you must know some basic comparison scales, for example, as
$n\rightarrow \infty$, and fixed
$a>0, b>0, c>1$ and any real
$d$,
$$d \ll \log \log n \ll \log^a n \ll n^b \ll c^n \ll n! \ll n^n$$
Where I write $a_n \ll b_n$ iff $\frac{a_n}{b_n} \rightarrow 0$ (this is not a standard notation !)
Of course, there are many other possible asymptotic comparisons, these are just the most frequent.
You have also some allowed operations, for example,
- if $\xi>1$ is a fixed real and $1 \ll a_n \ll b_n$, then $\xi^{a_n} \ll \xi^{b_n}$.
- if $s_n \ll a_n$ and $s_n \ll b_n$, and if $a_n \ll b_n$, then $a_n + s_n \ll b_n + s_n$.
You prove such things by computing the limit. Taking $\log$ as you did may be very useful (for example in the first case above).
Finally, you have to apply these comparisons to your case, and sometimes it's a bit tricky, but honestly here it's not.
- $n^2 \ll 2^n$ so $2^{n^2} \ll 2^{2^n}$
- $2 \ll n$, so $2^{2^n} \ll
n^{2^n}$. If in doubt, write the quotient
$a_n=\left(\frac{2}{n}\right)^{2^n}$, and since
$\frac{2}{n}<\frac{1}{2}$ as soon as $n>4$, you have $a_n \rightarrow
0$
- $1 \ll \log n $, so $n^2 \ll n^2 \log n$, and since $n \ll n^2$, you have $n \ll n^2\log n$.
- $n \ll n^2$ so $2^n \ll 2^{n^2}$, and also $\log n \ll n$ so $n^2 \log n \ll n^3$. Then $n^3 \ll 2^n$, hence $n^2\log n \ll n^3 \ll 2^n \ll 2^{n^2}$, and especially $n^2 \log n \ll 2^{n^2}$.
When you have a doubt, write what the comparison means as a limit, and compute the limit.
And remember, these comparisons are asymptotic. Sometimes the smallest $n$ such that the inequality really holds may be very large, but it's nevertheless only a fixed, finite number. You may have inequality for $n> 10^{10^{10}}$ for example, so trying to plot things is often hopeless.
If you want to know more about such methods, there are good readings, such as Concrete Mathematics, by Graham, Knuth and Patashnik.
Best Answer
First term: $(n \log n + 1)^2 = (n^2 (\log n)^2 + 2 n \log n + 1) = O(n^2 (\log n)^2)$
Second term: $(\log n + 1)(n^2 + 1) = (n^2 \log n + n^2 + \log n + 1) = O(n^2 \log n)$
Now, add two terms and apply the rule for sum of two functions that you have mentioned. You should get $O(n^2 (\log n)^2)$