算法导论习题解答 4.1-2

4.1-2 证明T(n)=2T(?n/2?)+n的解为O(nlgn)。证明这个递归的解也是Ω(nlgn),得到的解为Θ(nlgn)。
证明：

（1）假设T(?n/2?)<=c?n/2?lg(?n/2?)。则有：
??????????????? ?T(n)<=2(c?n/2?lg(?n/2?))+n
?????????????????????? <=cnlg(n/2)+n
?????????????????????? =cnlgn-cnlg2+n
?????????????????????? =cnlgn-cn+n?? (1)

????????如果c>=1，则有 (1)<=cnlgn。所以T(n)=2T(?n/2?)+n的解为O(nlgn)。

（2）假设T(?n/2?)>=c?n/2?lg(?n/2?)。则有：
????????????? T(n)>=2(c?n/2?lg(?n/2?))+n?
????????????????????>=c(n-1)lg(n/4)+n
??????????????????? =cnlgn-clgn-cnlg4+clg4+n? (1)?
????????若c足够小，有(1)>=cnlgn, 所以T(n)=2T(?n/2?)+n的解为Ω(nlgn)。

综上，T(n)=2T(?n/2?)+n的解为Θ(nlgn)。

?