4.3.md

Exercises 4.3-1

---

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

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

b.  = 4T(n/2)+n^2 )

c.  = 4T(n/2)+n^3 )

Answer


a.  )

b.  )

c.  )

Exercises 4.3-2

---

The recurrence T(n) = 7T (n/2)+n2 describes the running time of an algorithm A. A competing algorithm A′ has a running time of T′(n) = aT′(n/4) + n2. What is the largest integer value for a such that A′ is asymptotically faster than A?

Answer

根据主定理，算法A的运行时间为 = \Theta(\lg{7})\ \approx n^{2.8} )

A'的运行时间在a > 16时超过n^2,此时

 = \Theta(n^{\log_{4}{a}}) < \lg{7} = \log_{4}{49})

所以最大值为48

Exercises 4.3-3

---

Use the master method to show that the solution to the binary-search recurrence T(n) = T (n/2)

• Θ(1) is T(n) = Θ(lg n). (See Exercise 2.3-5 for a description of binary search.)

Answer


so the solution is Θ(lgn).

Exercises 4.3-4

---

Can the master method be applied to the recurrence  = 4T(n/2) + n^2 \lg{n} ) Why or why not? Give an asymptotic upper bound for this recurrence.

Answer


The problem is that it is not polynomially larger. The ratio   / n^{\log_{b}{a}} = \lg{n}) is asymptotically less than  for any positive constant 

Exercises 4.3-5

---

Consider the regularity condition af (n/b) ≤ cf(n) for some constant c < 1, which is part of case 3 of the master theorem. Give an example of constants a ≥ 1 and b > 1 and a function f (n) that satisfies all the conditions in case 3 of the master theorem except the regularity condition.

Answer

let

a = 1
b = 2
f(n) = 2 - cos(n)

我们需要证明

}) < cn \\ ~ \Rightarrow c > \frac{2- \cos(n/2)}{2} \\ ~ \Rightarrow c > \frac{3}{2} )

---

Follow @louis1992 on github to help finish this task.