Self doubt

Question

How  $O(n)+O(n)+O(n)+O(n)+O(n)+….+O(n)=O(n^2)$ but $\neq O(n)$

please explain it.

Answer 1

O(n) can be written as O(1) or O(2) or O(3) or O(4) or o(5).. ......O(n)

So O(1)+O(2)+O(3)+......O(n)

O(1+2+3+4......+n)

O(n^2)

Comments

As the definition of O(n) suggests if two functions f(n) and g(n) then f(n) = O{g(n)} iff

                            f(n) <= k * g(n) , n >= certain finite value

so it is never possible that O(n) = O(1) or O(2)……

because O(n) $\nleqslant$ k*1 or k*2…….

---

@Gopal6854 

What if my f(n) = Constant 

I'm thinking that

Proof by contradiction: 

Assume what the answer written is correct 

when we assume O(n) as O(1) all the time ( nothing is stopping us )

if this is the case then final result would be O(n) which means that out problem doesnt take more than n time which is clearly incorrect

---

[ Jiren ]

I think I understand where have I mistaken.

O(n) means the set of all the possible functions where the highest growing term is less than equal to n (highest growing term $\leq$n).

Ex: 2n+3 $\in$ O(n), 1 $\in$ O(n), 1000 $\in$ O(n), logn + 34 $\in$  O(n)

Now if we take f(n) = 1, g(n) = n, then:

               1 $\leq$ k*n    $\Rightarrow$1 = O(n)  $\Rightarrow$f(n) = O(n)

and also if we take g(n) = 1:

               1 $\leq$ k*1 $\Rightarrow$1 = O(1) $\Rightarrow$ f(n) = O(1)

But it does not mean that O(n) = O(1)

because f(n) = O(n) actually means f(n) $\in$ O(n) and f(n) = O(1) means f(n) $\in$ O(1)

But we can say that O(1) $\subset$ O(n), because all functions is available in O(n) which are in O(1) but converse is not true.

Please correct me if I have said anything wrong!!

---

@Gopal6854

when we see O() in an expression/formula then instead of seeing as a set , we will see it as an anonymous function ( This is given in CLRS )

Answer 2

O(n)+O(n)+……..n times = n*O(n) = O(n^2)

Comments

can we multiply like this??

---

Yes we can.

n*O(n) = O(n^2)

in this equation if we choose any function from O(n) in the left side and then we multiply it with n then we can always get a function that is in O(n^2).

Ex: 2n+3 $\in$ O(n) then n*(2n+3) $\in$ O(n^2)

       logn $\in$ O(n) then n*logn $\in$ O(n^2)