The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 votes

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

  1. $O(n)$
  2. $O(n^2)$
  3. $O(n^3)$
  4. $O(3n^2)$
  5. $O(1.5n^2)$
asked in Algorithms by Veteran (52k points)
edited by | 1.4k views
Is it possible to read whats under $\Sigma$?
@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(n3)

3 Answers

+29 votes
Best answer

This is $N$ added itself $N$ times. So it is $N^2$ . Even if you consider as sum of $O(1) + O(2) + .. O(n-1) + O(N)$. it will add up to $N^2$

So answer is

A) $O(N)$ this is false.

B,C,D,E ) All of this are true. We have $N^2$ here, so all options apart from A are correct.

In fact B = D = E this three options are same. and $N^3$ is always upper bound of $N^{2}$. So $O(N^3)$ is also true.


PS: $∑ (K=1$ to $n)$ $O(K)$ is never equal to $n$ functions. It is always equal to one single function. 

It can be written as $c.1+c.2+c.3$ and so on which results in $O(N^2)$ (source Cormen)

answered by Boss (41k points)
edited by
I think answer should be O(n^3) this is how i think of the answer

$\sum 1<=k<=n   O(n)$

=>$O(n)\sum 1<=k<=n k$  {k as some constant}

=>$O(n)\sum 1<=k<=n 1+2+3+.....+n$


+6 votes
except option A all are true..
out of these four options  option B,C,D are same. Answer should  b B,C,D..
answered by Veteran (59.7k points)

C. is O(n3). So, it's not possible.

Why not? It is big O. Also why not option e?
Oh, yes. BCDE should be the answer.

B, C, D, E should be the answer. But in case there are multiple correct options present, then the Tightest Upper Bound should always be chosen. In this case, TUB = O(n2). Hence, option B

–6 votes
c is the answer.
answered by (-1 points)
How, Please explain

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,084 answers
70,992 users