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

Time complexity analysis of recursive algorithms by solving recurrence relation using back - substitution method

#recurrence
#timecomplexity
#datastructures
#algorithm

[shreesidhinair]

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

[unknownunknown]

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
😃😃😃😃

[mdlwlmdddwd]

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