The Gateway to Computer Science Excellence
+26 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)$
in Algorithms by Veteran (52.3k points)
edited by | 2.1k 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)

4 Answers

+35 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)

by Boss (42.1k 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$


+7 votes
except option A all are true..
out of these four options  option B,C,D are same. Answer should  b B,C,D..
by Veteran (61k 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

0 votes
It'll be easier to replace $O(n)$ by some expression which is equal to $O(n)$. We can take $n$, or $n+5$, or $n/2$ or $3n$ — any such expression where the degree of n is 1, and other factors are independent of n.

Let's take $n$ for simplicity.


Then, the summation equation will be: $1+2+3+4+5+...+n$

=> $\frac{n(n+1)}{2}$

Which is $O(n^2)$
by Loyal (7.9k points)
–6 votes
c is the answer.
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
50,834 questions
57,838 answers
108,342 users