Dark Mode

9,550 views

38 votes

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

- $O(n)$
- $O(n^2)$
- $O(n^3)$
- $O(3n^2)$
- $O(1.5n^2)$

0

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

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

0

46 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) + \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)

what is wrong with @Arnab Mandal’s approach?

if **∑(k=1 to n)O(n)** then here the summation must be performed on some variable **k** .

so we can take **O(n)** out and then it will result in **O(n^3).**

why this is wrong?

1

6 votes

$$\begin{equation} \sum_{k=1}^{n} O(n) \end{equation}$$

Here, $k$ is just a dummy variable that is just 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)$

0

edited
Jan 16
by jaffreyjoy

O(N) + O(N) + …..+ O(N) = O(N)? Why cant this be correct?

It would be correct if $O(n)$ was being added for some constant $c$ times where $c \ll n$, but over here the number of times it is being added is a function of $n$ (in this case that function being $n$ itself) so even asymptotically we cannot ignore its(the no. of times its being added i.e. $n$) significance in the final result.

Edit: asymptomatically asymptotically...covid lingo doesn't wear out so easily ig

2

2 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)$

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