Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

According to the book "Introduction to Algorithms" a function that has the following form
$f(n)=an+b$
belong to $O(n^2)$ , and that this can be easily proven if we set
$c = a +|b|$
But I don't get it, it still seems to belong to $O(n)$.

share|improve this question
4  
Note big O is an upper asymptomic bound, not strict bound. So it will also fit to $O(n^5)$, $O(n^{99})$, and so on. –  Studentmath Jun 11 at 15:41
    
It belongs in $O(n)$ and because $O(n)⊂O(n^2)$ , it belongs in $O(n^2)$ as well?<br/>If Big-O were strict it would belong in $O(n)$ right? –  QxFFu Jun 11 at 15:44
    
$O(n)\subset O(n^2)$ , but I am pretty sure you mean that so yes. –  Studentmath Jun 11 at 15:46
    
@QxFFu You meant $O(n)\subset O(n^2)$. –  Andreas Blass Jun 11 at 15:46
    
@AndreasBlass Yes thats what I meant, thanks all for your fast answers. –  QxFFu Jun 11 at 15:48

2 Answers 2

up vote 0 down vote accepted

Everything in $O(n)$ is also $O(n^2)$. Recall that a function f(n) is O(n) if $f(n) \leq cn$ for sufficiently large $n$ and some constant $c>0$. Well, if $f(n) \leq cn$, then it's also the case that $f(n) \leq c n^2$ for all appropriately large $n$, so f(n) is $O(n^2)$ as well.

share|improve this answer

To be strict: $\forall n>N \ an +b <an^2 +b n^2 = (a+b)n^2 = O(n^2)$ hence the result, a very loose one of course.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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