The Gateway to Computer Science Excellence
0 votes
79 views
O(n-1)+O(n)=O(n)
O(n/2)+O(n)=O(n)
but O(1)+O(2)+O(3)+...+O(n)=O(n(n+1)/2)=O(n^2)
why?
in Algorithms by (175 points) | 79 views

2 Answers

+1 vote

When you add constant time complexities N times, you end up getting N.O(1) = O(N).

  • O(n-1)+O(n)=O(n) ; we are not adding n times . 

by Boss (35.7k points)
0

So when we are solving computations where O(1) or O(constant) is involved, then how do we know whether to involve that in the calculation or to ignore it. For e.g if O(1)+O(2)+O(3)+...+O(logn)+O(n) is there, then do we ignore the constant parts of the beginning?

0 votes

f(a)<=O(x): It means for function f(a) upper value cant go beyond x, so max value this function can attain  is x.(not quoting from any textbooks just in simple terms i briefed it)

And as far as we are concerned we need to give closest upper bound as we can write many upper bound for above given expression.

exp1+exp2+......+exp N=exp   always take max (exp1,exp2+...exp N) in calculating upper bound if like this is the given qsn and write every exp as max of the given, if for example exp1 is max than exp1+exp1+exp1+.....exp1(ntimes) this way you will give nearest and closest to upper bound for given expression.

Now coming to your qsn why ,

O(n-1)+O(n)=O(n) , we need to give upperbound for this expression ,as we can see max value it can attain is n, let see how

for O(n-1) we can write its upper bound as O(n) and for exp2 its already said max it can has is O(n).

so, you can write it as O(n)+O(n)=O(2n)=O(n) as we know O(c.n)=O(n)

Similarly, O(n/2)=O(n) and whole expression can be written as O(n)+O(n)=O(n)

now for your better understanding, we can rewrite above given exprsn as O(n)+O(n-1)+O(n-2)+O(n-3)+O(n-4)+...........+O(1) to find its upper bound you can again rewrite as O(n)+O(n)+O(n)+O(n)......+O(n)(n times)=O(n*n)=O(n^2)

by Active (3.9k points)
0

while trying to solve this, intuitively i got two approaches, one is as you mentioned, the other one is as follows:

O(1)+O(2)+O(3)+...+O(n-2)+O(n-1)+O(n)

=>O(1)+O(2)+O(3)+...+O(n-2)+O(n) [since O(n-1)+O(n)=O(n)]

=>O(1)+O(2)+O(3)+...+O(n-2)+O(n) 

=>O(1)+O(2)+O(3)+...+O(n)  [since O(n-2)+O(n)=O(n)]

after n steps

=>O(1) +O(n)=O(n)

So where exactly am in going wrong in this approach?

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,647 questions
56,508 answers
195,529 comments
100,966 users