4.1.md

Exercises 4.1-1

---

Show that the solution of is O(lg n).

Answer

我们猜想

Exercises 4.1-2

---

We saw that the solution of is O(n lg n). Show that the solution of this recurrence is also Ω(n lg n). Conclude that the solution is Θ(n lg n).

Answer

我们假设

Exercises 4.1-3

---

Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition T (1) = 1 for the recurrence (4.4) without adjusting the boundary conditions for the inductive proof.

Answer

我们假设

Exercises 4.1-4

---

Show that Θ(n lg n) is the solution to the "exact" recurrence (4.2) for merge sort.

Answer

我们假设

我们假设

Exercises 4.1-5

---

Show that the solution to is O(n lg n).

Answer

我们假设

Exercises 4.1-6

---

Solve the recurrence  by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

Answer

设n = lgn,得到新的递归式

再令S(n) = T(2^n)可以得到

按照前面的方法解这个递归式即可

---

Follow @louis1992 on github to help finish this task.