The Gateway to Computer Science Excellence

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

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

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

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,834 questions

57,838 answers

199,510 comments

108,342 users