I am to find the least integer $n$ such that $f(x)$ is $O(x^n)$ for the following functions:
$\begin{equation} (a) f(x) = 2x^2 + x^7 log(x) \end{equation}$
$\begin{equation} (b) f(x) = 3x^9 + (logx)^4 \end{equation}$
$\begin{equation} (c) f(x) = (x^4 + x^2 + 1) / (x^4 + 1) \end{equation}$
$\begin{equation} (d) f(x) = (x^3 + 5log(x)) / (x^4 + 1) \end{equation}$
We spent less than two hours covering this information, and normally I would not ask a question that I had so little understanding of, but I'm struggling to find explanations online. I understand that there is a "hierarchy" of big O constants, wherein if a function has more than one of these terms you can drop the lowest (such as, $f(x) = x^5 + log(x)$ , where you would drop the $log(x)$ and have $O(x^5)$).
However, for example in problem $a$, I'm unclear what to do when there's an $x^7$ in front of the log(x) and how to factor that into the $x^2$ that precedes it.
In $b$, I'm unclear how $log(x)$ being raised to a power affects big O.
In $c$, I feel like since the order of $x^4$ is higher than that of $x^2$, we should be able to drop the $x^2$ and just consider the whole function $O(1)$ but I don't know if that's correct.
In $d$, I thought we could just drop the $5log(x)$ since $nlog(n)$ is lower than $x^3$ or $x^4$ on the "cheat sheet" at bigocheatsheet.com, but then we would be left with $x^3/x^4$ , which is less than one so we can't find an integer $n$ for it.
I may be misunderstanding all of this. If anyone could offer an explanation for all or any of these parts, it would be enormously appreciated. Thank you
$\endgroup$ 01 Answer
$\begingroup$Any polynomial will eventually outpace $\log x$, so $\log^c x$ is $O(n^\epsilon)$ for every $\epsilon > 0$.
So for a, $x^7 \log x$ grows asymptotically faster than $x^7$ but slower than $x^{7 + \epsilon}$ for every $\epsilon > 0$. The question is careful to ask for the smallest power that will work...
For b, $\log^c x$ is still dominated by any positive power of $x$, so it has no effect on the big-Oh when added to $3x^9$.
For c, you're right. For large $x$, the ratio approaches $1$, so it is O(1).
For d, for large $x$ the ratio approaches $0$, which is still O(1).
$\endgroup$ 2
