4.2 - Clrs — ContextQMD

Exercises 4.2-1

Use a recursion tree to determine a good asymptotic upper bound on the recurrence . Use the substitution method to verify your answer.

`Answer`

树的高度是lgn,有3^lgn个叶子节点.

我们猜想

Exercises 4.2-2

Argue that the solution to the recurrence , where c is a constant, is Ω(nlgn) by appealing to the recurrsion tree.

`Answer`

最短的叶子高度是lg3n,每一层都要cn.也就是说，只考虑最短叶子的那一层（忽略其他层）已经有cnlg3n.

Exercises 4.2-3

Draw the recursion tree for ,where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method.

`Answer`

很明显是n^2的级别

我们假设

Exercises 4.2-4

Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(n - a) + T(a) + cn, where a ≥ 1 and c > 0 are constants.

`Answer`

我们假设

另外一个方向的证明和这个基本一样.

Exercises 4.2-5

Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(αn) + T((1 - α)n) + cn, where α is a constant in the range 0 <α < 1 and c > 0 is also a constant.

`Answer`

可以假设α < 1/2,因此树的高度有

Follow @louis1992 on github to help finish this task.