1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I'm at a bootcamp and they have their own textbook that is used within the bootcamp. I don't want to give out the name $\endgroup$ – MickeyTheMouse Aug 6 '18 at 20:26
  • 5
    $\begingroup$ Big-O notation just gives an upperbound. $O(n^5)$ contains (among many other things) every polynomial of degree $5$ and less. So the book is correct, but it is also $O(n^4)$. Just like $4\leq 5$ and also $4\leq 4$. $\endgroup$ – Derek Elkins left SE Aug 6 '18 at 20:32
  • 2
    $\begingroup$ @DerekElkins repost as answer $\endgroup$ – koverman47 Aug 6 '18 at 20:47
5
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Another unfortunate inconsistency is writing $=$ when $\in$ would be more correct, since $O(f(n))$ really describes the set of functions that do not grow significantly faster than $f(n)$. If you correctly write $n^4… \in O(n^5)$, it should be immediately obvious that since $n^4… \in O(n^4)$ and $O(n^4) \subset O(n^5)$, it follows that $n^4… \in O(n^5)$. $\endgroup$ – Jörg W Mittag Aug 9 '18 at 16:20
  • $\begingroup$ @JörgWMittag I agree. For some reason, people prefer $=$ when conceptually and formally, it's really $\in$ (or in some cases $\subseteq$). $\endgroup$ – 6005 Aug 9 '18 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.