recategorized by
12,589 views
41 votes
41 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)$
recategorized by

5 Answers

Best answer
48 votes
48 votes

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

So, the answer is:

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

$(B, C, D, E )$ All of this is 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 the upper bound of $N^{2}$. So $O(N^3)$ is also true.


PS: $\displaystyle{} \sum (K=1 \;\text{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)

edited by
11 votes
11 votes

$$\begin{equation} \sum_{k=1}^{n} O(n) \end{equation}$$
Here, $k$ is just a dummy variable that is used for the summation purpose.
It has nothing to do with the function $O(n)$

$O(g(n)) = c\cdot g(n)$ by definition and here $g(n) = n$

So,
\begin{align*} \sum_{k=1}^{n} O(n) &= O(n) + O(n) + … + O(n) &&\\ &= c\cdot g(n) + c\cdot g(n) + … + c\cdot g(n)  &&\\ &= \underbrace{c \cdot n + c \cdot n +… + c \cdot n}_\textrm{(k=1 to n) i.e. n times} &&\\ &= c \cdot n \cdot n &&\\ &= c \cdot n^2 &&\\ \end{align*}
The answer therefore is any function i.e. $\geq O(n^2)$ namely all options for this question except option (A) i.e. $O(n)$

edited by
9 votes
9 votes
except option A all are true..
out of these four options  option B,C,D are same. Answer should  b B,C,D..
3 votes
3 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)$
Answer:

Related questions

19 votes
19 votes
3 answers
1
Kathleen asked Sep 29, 2014
4,142 views
What does the following code do?var a, b: integer; begin a:=a+b; b:=a-b; a:a-b; end;exchanges $a$ and $b$doubles $a$ and stores in $b$doubles $b$ and stores in $a$leaves ...
28 votes
28 votes
3 answers
2
Kathleen asked Sep 29, 2014
4,395 views
Let $A$ and $B$ be sets with cardinalities $m$ and $n$ respectively. The number of one-one mappings from $A$ to $B$, when $m < n$, is$m^n$$^nP_m$$^mC_n$$^nC_m$$^mP_n$
27 votes
27 votes
3 answers
4
Kathleen asked Sep 29, 2014
6,849 views
Let A be a finite set of size n. The number of elements in the power set of $A\times A$ is:$2^{2^n}$$2^{n^2}$$\left(2^n\right)^2$$\left(2^2\right)^n$None of the above