gate 1987

Question

In GATE 1987 question, order of  $\Sigma$$O(n)$ was found to be $O(n^2)$.

Similarly, what will be the answer for order of $\Sigma$$O(n^2)$ ? Will it be of $O(n^3)$ ?

Thanks!

Answer 1

∑O(n) = $\sum _{i=1}^{n}$ O (n) = O(n)  $\sum _{i=1}^{n}$ 1 why because O(n) is constant

∑O(n) =  O(n)  { 1+1+1+...+1 ( n times ) }

          = O(n) . n = O(n²)  like that

 ∑O(n²) = O(n²)  { 1+1+1+...+1 ( n times ) }

             = O(n²) . n = O(n³) 

Comments

thank you so much :)

Answer 2

This is the proof for the first part