**solve the following recurrence relations a. π(π) = π( π/4) + π( π/2 ) + π^2 b. T(n) = T(n/5) + T(4n/5) + n c. π(π) = 3π( n/4 ) + ππ^2 f. π(π) = (π/πβ5) * π(π β 1) + 1 g. π(π) = π(log π) + log π h. π(π) = π (π^ 1/ 4) + 1 i. π(π) = π + 7 βπ β π(βπ) j. π(π) = π ( 3π/4 ) + 1/root(n)**

The **Answer to the Question**

is below this banner.

**Here's the Solution to this Question**

a.

$T(n)=n^2+5n^2/16+25n^2/256+...=n^2/(1-5/16)$

$T(n)=O(n^2)$

c.

Comparing withΒ $T(n)=aT(n/b)+f(n)$Β :

$a=3,b=4$

so, we have:

$f(n)=\Omega(n^{log_ba})=\Omega(n^{log_43})$

by Master Theorem:

$T(n)=\Theta(f(n))=\Theta(n^2)$

b.

additive term is exactly the current subproblem size, so T(n) is simply the sum of all numbers that appear in this tree. the:

$T(n)\ge nlog_5n$Β andΒ $T(n)\le nlog_{5/2}n$

so,

$T(n)=\Theta(nlogn)$

g.

for the upper bound:

$T(n)=O(logn)$

alsoΒ $T(n)=\Omega(logn)$

so,

$T(n)=\Theta(logn)$

j.

using Master Theorem:

$f(n)=O(n^{log_{4/3}3})$

so,

$T(n)=\Theta(n^{log_{4/3}3})$

h.

$π(π) = π (π^{ 1/ 4}) + 1=π (π^{ 1/ 16}) + 2=π (π^{ 1/ 64}) + 3=π (π^{ 1/ 4^n}) + n$

$T(n)=O(n)$

i.

$π(π) = π + 7 π(\sqrtπ)\sqrt n=7\sqrt n(7T(n^{1/4})n^{1/4}+n^{1/2})+n=$

$=7^kn^{1/2+1/4+1/8+...+1/2^k}T(n^{1/2^k})+...+n$

$1/2+1/4+1/8+...+1/2^k=1-1/2^k$

letΒ $n^{1/2^k}=2$Β , then:

$π(π)=7^nT(2)n/2+...+n$

$π(π)=O(7^nn)$

f.

$π(π) = (π/(πβ5)) π(π β 1) + 1$

$T(n)=(\frac{n}{n-5})^{n-1}T(1)+(\frac{n}{n-5})^{n-2}+...+1$

$T(n)=O(1)$