What to use for this Master or Substitution Method ?
T(1) = 1, and for all n ≥ 2 a power of 2, T(n)=2T(n/2) + 6n − 1.
If it is possible in Master Method how ?
Even,Substitution is also accecpted here.
Edit: In substitution Method
Suppose T(1) = 1, and for all n ≥ 2 a power of 2, T(n)=2T(n/2) + 6n − 1.
If n is large enough, then by repeated substitution,
T(n)=2T(n/2) + 6n − 1 (after one substitution)
= 2(2T(n/4) + 6n/2 − 1) + 6n − 1
= 4T(n/4) + (6n − 2) + (6n − 1) (after two substitutions)
= 4(2T(n/8) + 6n/4 − 1) + (6n − 2) + (6n − 1)
= 8T(n/8) + (6n − 4) + (6n − 2) + (6n − 1) (after three substitutions).
Therefore, after i substitutions,
$T(n) = 2^{i}T(n / 2^{i}) + 6in - \left ( \sum_{j = 0}^{i -1} 2^j\right )$
This can be verified easily by induction. Hence, taking i = log n,
$T(n) = nT(1) + 6nlogn - \left ( \sum_{j = 0}^{logn -1} 2^j\right )$
= n + 6n log n − (2log n − 1)
= 6n log n + 1.