Use a recursion tree to determine a good asymptotic upper bound on the recurrence
. Use the substitution method to verify your answer.
树的高度是lgn,有3^lgn个叶子节点.
我们猜想
Argue that the solution to the recurrence
, where c is a constant, is Ω(nlgn) by appealing to the recurrsion tree.
最短的叶子高度是lg3n,每一层都要cn.也就是说，只考虑最短叶子的那一层（忽略其他层）已经有cnlg3n.
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.
很明显是n^2的级别
我们假设
我们假设
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.
我们假设
另外一个方向的证明和这个基本一样.
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.
可以假设α < 1/2,因此树的高度有
Follow @louis1992 on github to help finish this task.