1 votes 1 votes $\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) Algorithms asymptotic-notation + – piyushkr asked Dec 31, 2015 piyushkr 1.7k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes 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 Kumar answered Dec 31, 2015 Shashank Kumar comment Share Follow See all 2 Comments See all 2 2 Comments reply rajatmyname commented Aug 23, 2016 reply Follow Share 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 0 votes 0 votes Shashank Kumar commented Aug 23, 2016 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.