Self doubt

Question

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?

Answer 1

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 . 

Comments

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?

Answer 2

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)

Comments

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?