GATE CSE 1993 | Question: 8.7

Question

$\displaystyle \sum_{1\leq k\leq n} O(n)$, where $O(n)$ stands for order $n$ is:

• A. $O(n)$
• B. $O(n^2)$
• C. $O(n^3)$
• D. $O(3n^2)$
• E. $O(1.5n^2)$

Comments

@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

---

@venkat yes

even i approached the same way and got O(n³)

---

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).

Answer 1

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.