While wondering with recursive analysis I was encountered with a question which is t(n) = 2t(n/2) + 7 using substitution method

Question

I was able to solve this question a little bit but i was confused that I have to just ignore those constant number and focus of Big oh(n) only.
My answer was also getting different at assuming different time.

If anyone than help me to find the exact solution??

Answer 1

Here we are.... the given recursion is a binary tree... one root will have two branches...
if we keep substituting t(n/2) with the given recursion equation...
t(n) =2(2t(n/4)+7)+7
=2(2(2t(n/8)+7)+7)+7
=.....
=2(2(2(2....(2t(1)+7).....)+7)+7)+7)
=2^k t(1)+7+7*2+7*2*2+...7*2^(k-1)
=2^k t(1)+7(1+2+4+8.....2^(k-1))
here we have n/2^k~1
i.e n~2^k
logn=klog2
k=logn base2
keeping these values in the last equation
t(n) = nt(1)+7((2^k-1)/(2-1))
t(n)=nt(1)+7(2^k-1)
t(n)=nt(1)+7(2^logn base2 - 1)
t(n)=nt(1)+7(n-1)
t(n)= n(t(1)+7) -7
since t(1) and 7 are constants...
t(n) =an+b=O(n)

since we assume n to be very very high value... the constants were neglected as the effect they cause doesn't have much effect..