I'm going through an algorithms text book. One of the questions asks:
True or false?
$n + 2n^2 + 10n^4$ is $O(n^5)$.
This is marked as true.
Shouldn't it be $O(n^4)$? What am I missing here?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI'm going through an algorithms text book. One of the questions asks:
True or false?
$n + 2n^2 + 10n^4$ is $O(n^5)$.
This is marked as true.
Shouldn't it be $O(n^4)$? What am I missing here?
This is an unfortunate inconsistency (or at least a frequent confusion) in terminology. Formally speaking, people usually define big-oh to be an upper bound, so that means running in time $O(n^5)$ just means the running time is bounded by $n^5$ times some constant if $n$ is sufficiently large.
In other words, $n^4$ is $O(n^5)$ (and it's also $O(n^4)$, $O(n^9)$, and $O(n^{1000})$, as well as many other things). In your example, $n + 2n^2 + 10n^4$ is both $O(n^4)$ and $O(n^5)$.
The usual formal notation for an exact asymptotic analysis (i.e. something that is both an upper and lower bound) is big-theta, or $\Theta$. So you would say that $n + 2n^2 + 10n^4$ is $\Theta(n^4)$, but it's not $\Theta(n^5)$.
The reason I call this terminology "unfortunate" is that it confuses many people, including you (as evidenced by you asking this question). The problem is that in informal speech, and often even in papers, people say $O$ when they really mean $\Theta$: when someone refers to a $O(n)$ algorithm, or an $O(n^2)$ algorithm, they often really mean $\Theta(n)$ or $\Theta(n^2)$. While using $O$ is usually not technically incorrect, it is misleading when $\Theta$ would also be correct and more precise. This is something you have to get used to: recognizing whether the writer really means $O$, or whether they could have said $\Theta$.