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
    Commented Aug 5, 2017 at 11:44
  • $\begingroup$ @fade2black ah okay, I had missed the clause that $0 \le f(n)$. Thanks! $\endgroup$
    – A.K.
    Commented Aug 5, 2017 at 11:48
  • $\begingroup$ you can remove this question otherwise it will be reposted repeatedly. $\endgroup$
    – fade2black
    Commented Aug 5, 2017 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.
    Commented Aug 5, 2017 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
    Commented Aug 5, 2017 at 12:03

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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