CODEWITHSUNDEEP
algorithmtime-complexitycomplexity-theory
NARAYAN CHANGDER
NARAYAN CHANGDER

Reputation: 319

Time complexity of this series

How to find the time complexity of below series

enter image description here

Please tell me is this correct bound or not.

Upvotes: 0

Views: 169

Answers (3)

user1196549
user1196549

Reputation:

For complete rigor, the proof must be a little more sophisticated.

Let f be the function which is O*(2^k). If O*(2^k) is understood in the same sense as O(2^k), then for some m, k≥m => f(k)≤C B(n,k)2^k. The bounding needen't hold for k<m.

Then for n>m the summation must be split in two parts, 

Σ(k=1->n) B(n,k)f(k)
    ≤ Σ(k=1->m-1) B(n,k)f(k) + Σ(k=m->n) C B(n,k)2^k 
    = Σ(k=1->m-1) B(n,k)f(k) - Σ(k=1->m-1) C B(n,k)2^k + Σ(k=1->n) C B(n,k)2^k
    = C' + C 3^n.
    ≤ (C' + C)3^n.

Upvotes: 2

Lissedo
Lissedo

Reputation: 41

I think this is the correct bound.
According to the binomial theorem, we have:

the picture is here

Then let x = 1 and y = 2.

Upvotes: 4

palash kulshreshtha
palash kulshreshtha

Reputation: 587

With little cheating from math exchange to remember the sigma(0,n) nCk = 2^n.

(x+y)^n=nC0*x^n*y^0 + nC1*x^n-1*y^1......+nCn-1*x^1*y^n-1+nCn*y^n*x^0  --(1)

this is normal binomial expansion of any equation of above form. Hence on the same terms we can open the given equation 

(1+2)^n = nC0*1^n*2^0 + nC1*1^n-1*2^1 ......+ nCn-1*1^1*2^n-1 + nCn*2^n*1^0 --(2)
(1+2)^n = 1 + nC1*1^n-1*2^1 ......+ nCn-1*1^1*2^n-1 + nCn*2^n*1^0 --(3)
(1+2)^n = 1+nC1*1^n-1*2^1 ......+ nCn-1*1^1*2^n-1 + nCn*2^n*1^0 --(4)
((3)^n)-1 = nC1*1^n-1*2^1 ......+ nCn-1*1^1*2^n-1 + nCn*2^n*1^0 --(4)

Hence given the question is about bounds then -1 can be ignored and given bounds are correct

Upvotes: 1

Related Questions