Solving Recurrence relation- T(n)=2T(n/2)+1

[@shreesidhinair6278]

Sir you actually explained it in a very convincing manner. Thank you

[@turnereverett2363]

a tip : you can watch series on kaldrostream. Me and my gf have been using it for watching a lot of movies recently.

[@raphaelbranson5832]

@Turner Everett yup, been watching on kaldrostream for since december myself :D

[@tonytom3148]

Beautiful Explanation

[@connorcribley7795]

I can't thank you enough, sir!

[@Aryan_1238]

Super trick mathematic

[@kathyker3498]

thank you

[@sanatanbharat3647]

Please make more videos like this

[@crispinewachira9084]

How does 2k.2 - 2k - 1 become 2k - 1?

[@varshaeluru9816]

Yaaa how

[@tonytom3148]

two times 2k i.e 2k.2 is 4k ....... so (4k - 2k -1) = 2k -1@@varshaeluru9816

[@marwanfaisal]

can please solve this t(n)=2t(n/4)+1

[@saptarshibose9718]

Root n

[@saptarshibose9718]

Use masters theorem for divide recursion problems. It can be solved within 10 seconds

[@mdlwlmdd2dwd30]

Good breakdown but as a computer scientist. It is better to taking more abstract approach. T(n/2) already indicates it is log2_n Why? Base case T(1) = T(n/2) n/{2}^k, k =log 2_n , to make 1 Total work we can easily find by seeing 1+2+4+8...2^k total work by looking at non recursive function Summation 2^k = we can approximate 2^k with geometric series without going details as the constant doesnt matter. K is height. 2 ^ log2_n = n

[@marwanfaisal]

can please solve this t(n)=2t(n/4)+1 using recursion tree method

[@unknownunknown8699]

This analysis is wrong. we are using constant "1" here : T(n)=2T(n/2)+1 So even if we have 2^k = n then answer should be T(n)=2T(n/2)+1 T(n)=4T(n/4)+2 T(n)=8T(n/8)+3 ...... T(n)=2^kT(2^k/2^k)+ n so replace 2^k = n we get T(n)=n T(1) + 2^k log to base 2 of (n) = k so T(n)=n + logn T(n) = n 😃😃😃😃

[@gabriel.adeife]

You forgot to multiply the +1 in the equation. T(n/2) = 2T(n/4)+1 T(n)=2(2T(n/4)+1)+1 = 4T(n/4)+3 and so forth.