Solve recurrence using Master theorem

Question

$T(a)=0 \hspace{0.2cm} if \hspace{0.2cm} a=1$

$T(a)=2T(a/2) + ak \hspace{0.2cm} if \hspace{0.2cm} a=2^{p}, p>0$

where $a=\frac{n}{k}$

Answer: $\Theta (n \log (\frac{n}{k}))$, This is while (n/k) is power of 2.

How can I solve it using master theorem?

Answer 1

Forget all the complex part and just focus on the given recurrence relation.

$T(a) = 0$ if $a=1$

$T(a) = 2T(a/2) + ak$ if $a=2^p,p>0$

Since we are applying Master's theorem and in the above recurrence relation independent variable is 'a' (not 'n') we calculate $a^{log_b(c)} = a^{log_2(2)} = a$

Note here that we are comparing the above recurrence relation to the following generalized recurrence relation.

$T(a) = cT(a/b) + f(n)$

Now from Rule 3. of Master Theorem $T(a) = \theta{(aloga)} $

At last substitute the value of $a$ to get $T(a) = T(n/k) = \theta{\left(nlog\left(\frac{n}{k}\right)\right)}$