4.3-1 证明：T(n)=T(n-1)+n的解为O（
n2
）。
c(n−1)2+n≤n2cn2−2cn+c+n≤n2cn2−(2c−1)n+1≤n2
当c大于等于1时成立
4.3-2 证明：
T(n)=T(⌈n/2⌉)+1的解为O（lgn）
clgn2+1=clgn−clg2+1=clgn−c+1≤lgn
当c大于等于2时成立
4.3-3 我们看到
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
如果c>=1，则有 cnlgn-cn+n <=cnlgn。所以T(n)=2T(⌊n/2⌋)+n的解为O(nlgn)。
（2）
假设T(⌊n/2⌋)≥c⌊n/2⌋lg(⌊n/2⌋+dn)。则有：T(n)≥2(c⌊n/2⌋lg(⌊n/2⌋))+n≥c(n)lg(n/2)+n+2dn=cnlgn+(d−c)n+n+dn>=cnlgn+dn
若d>c， 所以T(n)=2T(⌊n/2⌋)+n的解为Ω(nlgn)。
综上，T(n)=2T(⌊n/2⌋)+n的解为Θ(nlgn)。
4.3-4 证明：通过做出不同的归纳假设，我们不必调整归纳证明中的边界条件，即可克服递归式（4.19）中边界条件T(1)=1带来的困难。
猜测为
T(n)≤cnlgn+cd
4.3-5 证明：归并排序的“严格”递归式（4.3）的解为θ（nlgn）
同4.3-3
4.3-6 证明：
T(n)=2T(⌊n2⌋+17)+n
的解为O（nlgn）。
解：不会
4.3-7~4.3-9待整理。
