41 votes 41 votes $\displaystyle \sum_{1\leq k\leq n} O(n)$, where $O(n)$ stands for order $n$ is: $O(n)$ $O(n^2)$ $O(n^3)$ $O(3n^2)$ $O(1.5n^2)$ Algorithms gate1993 algorithms time-complexity easy + – Kathleen asked Sep 29, 2014 • recategorized Apr 22, 2021 by Lakshman Bhaiya Kathleen 12.8k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Venkat Sai commented Nov 3, 2017 reply Follow Share @Arjun sir dont u think the question should be k from 1 to n sigma(O(k))?? else its looks like adding O(n) n times which gives O(n^3) as the only answer 0 votes 0 votes A_i_$_h commented Dec 22, 2017 reply Follow Share @venkat yes even i approached the same way and got O(n3) 0 votes 0 votes Kiyoshi commented Jun 25, 2021 reply Follow Share those who confused about O(n) or O(n^2). Look at this… Suppose our k goes from 1 to 8 so (basically n=8 here,…) Now, if you wanted to find value sharp at k=7(forget about sigma for a sec), So, how can you write.. either, you can write O(7) which leads to O(1) or constant time complexity Or O(n-1) leads to O(n) because you have assumed your n=8 So, taking all of worst cases leads to O(n^2). 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes I think answer Option A is absolutely fine why we are adding all these terms order must be the highest degree term when more than one terms with their order is in addition form. Jahanvi Pritam answered Jul 3, 2020 Jahanvi Pritam comment Share Follow See all 0 reply Please log in or register to add a comment.