4.5 The master method for solving recurrences

4.5-1

Use the master method to give tight asymptotic bounds for the following recurrences.

a. $T(n)=2T(n/4)+1$.

b. $T(n)=2T(n/4)+\sqrt{n}$.

c. $T(n)=2T(n/4)+\sqrt{n}\lg^2 n$.

d. $T(n)=2T(n/4)+n$.

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

a.

$$ \begin{aligned} a=2,b=4,n^{\log_{b}a}=n^{1/2},f(n)=1=O(n^{\log_{b}a-1/2})\cr T(n)=\Theta(n^{1/2})\cr \end{aligned} $$

b.

$$ \begin{aligned} a=2,b=4,n^{\log_{b}a}=n^{1/2},f(n)=n^{1/2}=\Theta(n^{\log_{b}a})\cr T(n)=\Theta(n^{1/2}\lg n)\cr \end{aligned} $$

c.

$$ \begin{aligned} a=2,b=4,n^{\log_{b}a}=n^{1/2},f(n)=n^{1/2}\lg^{2}n=\Theta(n^{\log_{b}a}\lg^{2}n)\cr T(n)=\Theta(n^{1/2}\lg^{3} n)\cr \end{aligned} $$

d.

$$ \begin{aligned} a=2,b=4,n^{\log_{b}a}=n^{1/2},f(n)=n=\Omega(n^{\log_{b}a+1/2})\cr \text{regularity condition: }af(n/b)=n/2\leq (1/2)n\cr T(n)=\Theta(n)\cr \end{aligned} $$

e.

$$ \begin{aligned} a=2,b=4,n^{\log_{b}a}=n^{1/2},f(n)=n^2=\Omega(n^{\log_{b}a+3/2})\cr \text{regularity condition: }af(n/b)=n/8\leq (1/8)n\cr T(n)=\Theta(n^2)\cr \end{aligned} $$

4.5-2

Professor Caesar wants to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen’s algorithm. His algorithm will use the divide-and-conquer method, dividing each matrix into $n/4\times n/4$ submatrices, and the divide and combine steps together will take $\Theta(n^2)$ time. Suppose that the professor’s algorithm creates a recursive subproblems of size $n/4$. What is the largest integer value of $a$ for which his algorithm could possibly run asymptotically faster than Strassen’s?

$$ \begin{aligned} n^{\log_{b}a}=n^{\log_{4}a} < n^{\lg 7}\cr \implies a < 49\cr \end{aligned} $$

4.5-3

Use the master method to show that the solution to the binary-search recurrence $T(n) = T(n/2) + \Theta(1)$ is $T(n) = \Theta(\lg n)$. (See Exercise 2.3-6 for a description of binary search.)

$$ \begin{aligned} n^{\log_{b}a}=n^{\log_{2}1}=1\cr f(n)=1=\Theta(n^{\log_{b}a}\lg^{0}n)\cr T(n)=\Theta(\lg n)\cr \end{aligned} $$

4.5-4

Consider the function $f(n) = \lg n$. Argue that although $f(n/2) < f(n)$, the regularity condition $af(n/b)\leq cf(n)$ with $a=1$ and $b=2$ does not hold for any constant $c<1$. Argue further that for any $\epsilon > 0$, the condition in case 3 that $f(n) = \Omega(n^{\log_{b}a+\epsilon})$ does not hold.

$$ \begin{aligned} &\forall c<1\cr &f(n/2)\leq cf(n)\cr \iff & \lg n-1\leq c\lg n\cr \iff & \lg n\leq 1/(1-c)\cr \iff & n\leq 2^{1/(1-c)}\cr \end{aligned} $$

so the regularity condition does not hold for $n\geq 2^{1/(1-c)}$

$$ \begin{aligned} n^{\log_{b}a}=n^{\log_{2}1}=1\cr \forall \epsilon>0\cr cn^{\epsilon}\leq \lg n \text{ does not hold for }n\to \infty\cr \end{aligned} $$

so $f(n) = \Omega(n^{\log_{b}a+\epsilon})$ does not hold.

4.5-5

Show that for suitable constants $a,b$, and $\epsilon$, the function $f(n)=2^{\lceil\lg n\rceil}$ satisfies all the conditions in case 3 of the master theorem except the regularity condition.

$$ \begin{aligned} a=1.1,b=1.2,n^{\log_{b}a}=n^{\log_{1.2}1.1}\cr f(n)\geq 2^{\lg n}=n\geq n^{\log_{1.2}1.1+\log_{1.2}1.001}\cr \implies \exist \epsilon>0 \text{ such that }f(n)=\Omega(n^{\log_{b}a+\epsilon})\cr \end{aligned} $$

$f(n)$ satisfies all the conditions in case 3 of the master theorem except the regularity condition.

$1.1f(\frac{1.3\cdot 2^k}{1.2})=1.1\cdot 2^{k+1}\leq cf(1.3\cdot 2^k)=c\cdot 2^{k+1}$ dose not hold for any c<1.