a. $\Theta (n^{4})$ a=2, b=2 by Master's theorem
b. $\Theta (n)$ a=1, b=10 by Master's theorem
c. $\Theta (n^{2}logn)$ a=16, b=4 by Master's theorem
d. $\Theta (n^{2})$ a=7, b=3 by Master's theorem
e. $\Theta(n^{log_{2}^{7}})$ a=7, b=2 by Master's theorem
f. $\Theta (\sqrt{n}*logn)$ a=2, b=4 by Master's theorem
g. Can't be solved by Master's theorem, use back substitution method
Detailed Solution:
b. T(n) = T($\frac{7n}{10}$) + n
a=1, b=$\frac{10}{7}$
Apply Master's theorem here:
$n^{log_{7/10}^{1}}$ = $n^{0}$ = 1
hence T.C will be $\Theta (n)$
g. T(n) = T(n-2) + $n^{2}$
Use back substitution method
T(n) = T(n-2) + $n^{2}$
T(n-2)= T(n-4) + $(n-2)^{2}$
T(n) = T(n-4) + $(n-2)^{2}$ + $n^{2}$
T(n) = T(n-6) +$(n-4)^{2}$ + $(n-2)^{2}$ + $n^{2}$
.
.
kth Term
T(n) = T(n-2k) + $(n-2(k-1))^{2}$ + $(n-2(k-2))^{2}$ + ..................+$(n-2)^{2}$ + $n^{2}$
Suppose 2k=n and t(0)=1 and k=$\frac{n}{2}$
= 1 + $2^{2}$ + $4^{2}$ + .......................+ $(n-2)^{2}$ + $n^{2}$
= 1 + $\sum_{i=0}^{\frac{n}{2}} (n-2i)^{2} \leq 1+ \sum_{i=0}^{n-1} (n-i)^{2}$
= 1 + $ \sum_{i=1}^{n} (n)^{2}$
= 1 + $\frac{n(n+1)(2n+1)}{6} = \Theta (n^{3})$
PS: Except problems b and g,others are simple problems and can directly be solved by Master's theorem!
