Skip to content

Latest commit

 

History

History
75 lines (49 loc) · 3.82 KB

4.2.md

File metadata and controls

75 lines (49 loc) · 3.82 KB

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

recursion tree

树的高度是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

recursion tree

很明显是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

recursion tree file:///Users/ganzhenchao/Workspaces/CLRS/C04-Recurrences/repo/s2/4.png

我们假设

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

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

recursion tree

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


Follow @louis1992 on github to help finish this task.