$\sum(range -> 1<=k<=n) O(n)$, where O(n) stands for order n is -
a) O(n) b) O(n2)
c) O(m3) d) O(3n2)
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(n2)
Hence ans: (b)
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(n2).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(n2).
If we had O(k) instead of O(n) then we would have written as the way you wrote.
64.3k questions
77.9k answers
244k comments
80.0k users