substitution or Master Method

Question

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.

Answer 1

given  Recurrence satisfy aT(n/b) + f(n) where a>=1, b>1, f(n) is polynomial of 'n'.

here a=2, b=2, f(n) = 6n-1 (Linear function in 'n')
Apply masters answer is Θ(nlogn).
https://en.wikipedia.org/wiki/Master_theorem

Comments

Substitution Method has some additional constant (See Edit in question) . So, in master method shall we able to derive the constant terms ?

---

no .. Master Method used to find Asymptotic value. in Asymptotic notation all constants considered as same ans it is  O(1).
To find constant term, use mathematical Procedure.

Answer 2

Yes i think possible . Replace the term 6n - 1 with some function say f(n)

Now expression becomes  :

T(N) = 2T(N/2) + f(n) where f(n) is O(n) because dominating factor in this polynomial function is n.

T(N) = 2T(N/2) + O(N)

Now apply Master's Method :

Ans is  $\Theta$ (nlogn) .