# strange choice of constant when showing $an + b = O(n^2)$ (“Introduction to Algorithms” book)

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?

• Because of requirement $an+b > 0$. It requires $0 \leq f(n)$ – fade2black Aug 5 '17 at 11:44
• @fade2black ah okay, I had missed the clause that $0 \le f(n)$. Thanks! – A.K. Aug 5 '17 at 11:48
• you can remove this question otherwise it will be reposted repeatedly. – fade2black Aug 5 '17 at 11:54
• 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.) – A.K. Aug 5 '17 at 11:57
• I have noticed that questions without accept are posted repeatedly by the @Community user, even though they have excellent answers. – fade2black Aug 5 '17 at 12:03

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