search
Log In
0 votes
178 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 178 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 . 

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)

1

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?

Related questions

1 vote
1 answer
1
168 views
What will be the time complexity of the following code? A() { int i,j,k,n; for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { for(k=1;k<=100;k++) { printf("ABCD"); } } } }
asked Oct 20, 2017 in Algorithms Manish Chetwani 168 views
0 votes
0 answers
2
122 views
I wanted to know how θ is derived for a problem. Can we write it directly Example n^4 + n^3+ n^2 Here worst case will be n^4 since it is the term with highest power(worst). Similarly can i get θ
asked Nov 25, 2017 in Algorithms aka 53 122 views
3 votes
2 answers
3
284 views
f(n) = $n*2^{n}$ g(n) = $e^n$ What is the relation b/w the asymptotic time complexities of f(n) and g(n)?
asked Aug 15, 2017 in Algorithms Manu Thakur 284 views
0 votes
2 answers
4
446 views
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
asked Mar 30, 2020 in Algorithms Lakshman Patel RJIT 446 views
...