The Gateway to Computer Science Excellence
+26 votes
2.1k views

$\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
0
Is it possible to read whats under $\Sigma$?
+1
1<=k<=n.
0
@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

@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
+1
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$

=>$n*n*(n-1)/2$

=>O(n^3)
+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)
0

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

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

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)
0
How, Please explain
Answer:

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
199,510 comments
108,342 users