4.4

Exercises 4.4-1

---

Give a simple and exact expression for nj in equation (4.12) for the case in which b is a positive integer instead of an arbitrary real number.

Answer

Exercises 4.4-2

---

Show that if , where k ≥ 0, then the master recurrence has solution Show that if .

Answer

Exercises 4.3-3

---

Show that case 3 of the master theorem is overstated, in the sense that the regularity condition af(n/b) ≤ cf(n) for some constant c < 1 implies that there exists a constant .

Answer

根据case3,我们有

变形一下

---

Follow @louis1992 on github to help finish this task.