$\star$ 4.7 Akra-Bazzi recurrences

$\star$ 4.7-1

Consider an Akra-Bazzi recurrence $T(n)$ on the reals as given in recurrence (4.22), and define $T'(n)$ as

$$ \begin{aligned} T'(n)=cf(n)+\sum_{i=1}^k a_iT'(n/b_i), \end{aligned} $$

where $c > 0$ is constant. Prove that whatever the implicit initial conditions for T(n) might be, there exist initial conditions for $T'(n)$ such that $T'(n) = cT(n)$ for all $n>0$. Conclude that we can drop the asymptotics on a driving function in any Akra-Bazzi recurrence without affecting its asymptotic solution.

assume $T'(n)=cT(n)$

$$ \begin{aligned} T'(n) & =cf(n)+\sum_{i=1}^k a_iT'(n/b_i)\cr & =cf(n)+\sum_{i=1}^k a_icT(n/b_i)\cr & =c(f(n)+\sum_{i=1}^k a_iT(n/b_i))\cr & =cT(n)\cr \end{aligned} $$

$T'(n)=T(n)$ holds only if the base case(initial conditions) that $T'(n)=T(n)$ for all $n<n_{}0$ is true

4.7-2

Show that $f(n)=n^2$ satisfies the polynomial-growth condition but that $f(n)=2^n$ does not.

$$ \begin{aligned} & \forall \phi \forall \psi:1 \leq \psi \leq \phi\cr & n^2/d\leq (\psi n)^2\leq dn^2\cr \iff & \max(1/\psi^{2})\leq d \wedge \max(\psi^{2}) \leq d\cr \iff & \phi^{2}\leq d\qquad(1)\cr & 2^n/d\leq 2^{\psi n}\leq d2^n\cr \iff & 2^{n-\psi n}\leq d\wedge 2^{\psi n-n}\leq d\qquad (2)\cr \end{aligned} $$

$d=\phi^{2}$ satisfies $(1)$, since $2^{(\psi-1)n}\to\infty$ therefore no constant $d$ satisfies $(2)$

4.7-3

Let f(n) be a function that satisfies the polynomial-growth condition. Prove that $f(n)$ is asymptotically positive, that is, there exists a constant $n_0\geq 0$ such that $f(n)\geq 0$ for all $n\geq n_0$.

$$ \begin{aligned} \exist \hat{n} \text{ that }\forall n > \hat{n}:\cr f(n)/d \leq f(\psi n) \leq df(n)\cr \implies 0\leq (d^2-1) f(n)\cr \because d>1\cr \therefore f(n)>0\cr \end{aligned} $$

$\star$ 4.7-4

Give an example of a function $f(n)$ that does not satisfy the polynomial-growth condition but for which $f(\Theta(n)) = \Theta(f(n))$.

• TODO

4.7-5

Use the Akra-Bazzi method to solve the following recurrences.

a. $T(n) = T(n/2)+T(n/3)+T(n/6)+n\lg n$.

b. $T(n) = 3T(n/3)+8T(n/4)+n^2/\lg n$.

c. $T(n) = (2/3)T(n/3)+(1/3)T(2n/3)+\lg n$.

d. $T(n) = (1/3)T(n/3) + 1/n$.

e. $T(n) = 3T(n/3) + 3T(2n/3)+n^2$.

a.

$$ \begin{aligned} & (\frac{1}{2})^p+(\frac{1}{3})^p+(\frac{1}{6})^p=1\cr \implies & p=1\cr T(n) & =\Theta(n^p(1+\int_{1}^{n}\frac{f(x)}{x^{p+1}}dx))\cr & = \Theta(n^1(1+\int_{1}^{n}\frac{x\lg x}{x^{2}}dx))\cr & = \Theta(n^1(1+\int_{1}^{n}\frac{\ln x}{x\ln 2}dx))\cr & = \Theta(n^1(1+\left[\frac{\ln^{2} x}{2\ln 2}\right]_{1}^{n}))\cr & = \Theta(n(1+\frac{\ln^{2} n}{2\ln 2}))\cr & =\Theta(n\lg^{2} n) \end{aligned} $$

b.

$$ \begin{aligned} & \frac{3}{3^p}+\frac{8}{4^p}=1\cr & \frac{3}{3^{1.5}}+\frac{8}{4^{1.5}}=3^{-(1/2)}+1\cr & \frac{3}{3^2}+\frac{8}{4^2}=\frac{5}{6}\cr \implies & 1.5<p<2\cr T(n) & =\Theta(n^p(1+\int_{1}^{n}\frac{f(x)}{x^{p+1}}dx))\cr & =\Theta(n^p(1+\int_{1}^{n}\frac{x^2/\lg x}{x^{p+1}}dx))\cr & =\Theta(n^p(1+\int_{1}^{n}\frac{1}{x^{p-1}\lg x}dx))\cr & =\Omega(n^p(1+\lg n\int_{1}^{n}\frac{1}{x^{p-1}}dx))\cr & =\Omega(n^p(1+n^{2-p}\lg n ))\cr & =\Omega(n^2/\lg n)\cr T(n) & =O(n^p(1+\lg 1(\text{regarded as constant})\int_{1}^{\sqrt{n}}\frac{1}{x^{p-1}}dx+\lg \sqrt{n}\int_{\sqrt{n}}^{n}\frac{1}{x^{p-1}}dx))\cr & = O(n^p(1+\Theta(n^{(p-1)/2})+\Theta(n^{p-1}/\lg n)))\cr & =O(n^2/\lg n)\cr \end{aligned} $$

c.

$$ \begin{aligned} & \frac{2}{3}(\frac{1}{3})^p+\frac{1}{3}(\frac{2}{3})^p=1\cr \implies & \frac{2+2^p}{3^{p+1}}=1\cr \implies & p=0\cr T(n) & =\Theta(n^p(1+\int_{1}^{n}\frac{f(x)}{x^{p+1}}dx))\cr & =\Theta(1+\int_{1}^{n}\frac{\lg x}{x}dx)\cr & =\Theta(\lg^{2}n) \end{aligned} $$

d.

$$ \begin{aligned} & \frac{1}{3}(\frac{1}{3})^p=1\cr \implies & p=-1\cr T(n) & =\Theta(n^p(1+\int_{1}^{n}\frac{f(x)}{x^{p+1}}dx))\cr & =\Theta(n^{-1}(1+\int_{1}^{n}\frac{1}{x}dx))\cr & =\Theta(n^{-1}(1+\left[lg n\right]_{1}^{n}))\cr & =\Theta(n^{-1}lg n)\cr \end{aligned} $$

e. $T(n) = 3T(n/3) + 3T(2n/3)+n^2$.

$$ \begin{aligned} & 3(\frac{1}{3})^p + 3(\frac{2}{3})^p=1\cr \implies & p=2\cr T(n) & =\Theta(n^p(1+\int_{1}^{n}\frac{f(x)}{x^{p+1}}dx))\cr & =\Theta(n^{2}(1+\int_{1}^{n}\frac{x^2}{x^3}dx))\cr & =\Theta(n^2\lg n) \end{aligned} $$

$\star$ 4.7-6

Use the Akra-Bazzi method to prove the continuous master theorem.

$$ \begin{aligned} & T(n)=aT(n/b)+f(n)\cr & \frac{a}{b^p}=1\cr \implies & p=\log_{b}a\cr T(n) & =\Theta(n^p(1+\int_{1}^{n}\frac{f(x)}{x^{p+1}}dx))\cr & =\Theta(n^{\log_{b}a}(1+\int_{1}^{n}\frac{f(x)}{x^{\log_{b}a+1}}dx))\cr & G(n)=\int_{1}^{n}\frac{f(x)}{x^{\log_{b}a+1}}dx\cr \text{case 1:} & \cr & f(n)=O(n^{\log_{b}a-\epsilon})(\epsilon>0)\cr G(n) & = O(\int_{1}^{n}\frac{1}{x^{1+\epsilon}}dx)\cr & = O(x^{-\epsilon})\cr T(n) & =\Theta(n^{\log_{b}a}(1+G(n)))\cr & = \Theta(n^{\log_{b}a})\cr \text{case 2:} & \cr & f(n)=\Theta(n^{\log_{b}a}\lg^{k}n)(k\geq 0)\cr G(n) & = \Theta(\int_{1}^{n}\frac{lg^{k}n}{x^{1}}dx)\cr & = \Theta(\lg^{k+1}n)\cr T(n) & =\Theta(n^{\log_{b}a}(1+G(n)))\cr & = \Theta(n^{\log_{b}a}\lg^{k+1}n)\cr \text{case 3:} & \cr T(n) & =\Omega(f(n))\cr & f(n)=\Omega(n^{\log_{b}a+\epsilon})(\epsilon>0)\cr &\text{if } af(n/b)<cf(n)\text{ for some }c<1\cr G(n) & = O(f(n)\int_{1}^{n}\frac{1}{x^{\log_{b}a+1}}dx)\cr & = O(\frac{f(n)}{x^{\log_{b}a}})\cr T(n) & =\Theta(n^{\log_{b}a}(1+G(n)))\cr & =O(f(n))\cr T(n)& =\Theta(f(n)) \end{aligned} $$