Below question asked in GATE 1993. In this 1<=k<=n mentioned however k not using anywhere in notation.

Question

$\sum(range -> 1<=k<=n) O(n)$, where O(n) stands for order n is -

a) O(n)                b)   O(n²)

c)  O(m³)       d) O(3n²)

Answer 1

Yes,'K' is used as follows:

1<= k<= n => we have add O(n) 'n' times since 'k' is 1 to n. 'K' is like iterator .

Hence : O(n) +O(n) +O(n) +...........n times  =  nO(n) = O(n²)

Hence ans: (b)

Comments

Shashank Sir, I think instead of O(n) in the question it should be O(k) because k iterates from 1 to n and it results to O(1)+O(2)+O(3)+.....O(n)=O(n²).Please clarify my doubt

---

Here O(n) is independent of k and k varies from 1 to n.So O(n) will be added n times.Hence n*O(n) = O(n²).

If we had O(k) instead of O(n) then we would have written as the way you wrote.