In the third edition of Introduction to Algorithms, the authors state:

... when $a$ > 0, any linear function $an+b$ is $O(n^2)$, which is easily verified by taking $c = a + |b|$ and $n_0 = max(1, -b/a).$

[In the above, $c$ and $n_0$ come from the standard definition of big-oh:

$f(n)$ is in $O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le cg(n)$ for all $n \ge n_0$.]

I have no trouble accepting that $an+b \in O(n^2)$, but I'm questioning the motivation/origin of the weird choice of $n_0$.

If we assume that $ n \ge 1$, then, since $a > 0$, we have $an^2 \ge an$ and since $n^2 \ge 1$ we have $|b|n^2 \ge |b| \ge b$, implying that $(a+|b|)n^2 \ge an+b$. So it seems that $n_0$ could simply have been taken as $1$. Or am I messing up somewhere?

  • $\begingroup$ Because of requirement $an+b > 0$. It requires $0 \leq f(n)$ $\endgroup$ – fade2black Aug 5 '17 at 11:44
  • $\begingroup$ @fade2black ah okay, I had missed the clause that $0 \le f(n)$. Thanks! $\endgroup$ – A.K. Aug 5 '17 at 11:48
  • $\begingroup$ you can remove this question otherwise it will be reposted repeatedly. $\endgroup$ – fade2black Aug 5 '17 at 11:54
  • $\begingroup$ Why do you feel I should remove it? I think it might help someone else making the same mistake as me. (btw if you were to post your comment as an answer I'd be happy to accept it.) $\endgroup$ – A.K. Aug 5 '17 at 11:57
  • $\begingroup$ I have noticed that questions without accept are posted repeatedly by the @Community user, even though they have excellent answers. $\endgroup$ – fade2black Aug 5 '17 at 12:03

Because of the requirement $an+b>0$. The definition requires $0 \leq f(n)$.

| cite | improve this answer | |

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.