9,550 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)$

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

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

So, taking all of worst cases leads to O(n^2).

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$

$(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?

@Abhrajyoti00

@Pranavpurkar have u got the conclusion?for this question

except option A all are true..
out of these four options  option B,C,D are same. Answer should  b B,C,D..

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

I think O(2) or O(k) for some constant is always considered as O(1). So time complexity can be O(1)*n = O(n).

Where I am going wrong.

$$$$\sum_{k=1}^{n} O(n)$$$$
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)$

perfect!

@jaffreyjoy ,  If we are  given question like total complexity of [ O(n^2) + O (n) + O( n^3) ] we always choose the O(n^3) because it has greater complexity among all others

Then why can’t in this case:

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

edited

@jiminpark

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

@jaffreyjoy, Thanks got it !

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