算法导论习题解答 4.1-1
4.1-1 证明T(n)=T(⌈n/2⌉)+1的解为O(lgn)。证明：假设T(⌈n/2⌉)<=clg(⌈n/2⌉-b)+1,则有：
T(n)<= clg(⌈n/2⌉-b)+1
<= clg(n/2-b+1)+1
=clg((n-2b+2)/2)+1
=clg(n-2b+2)-clg2+1 (1)
如果b>=2 && c>=1,则有(1) <=clg(n-b)。
所以，T(n)=T(⌈n/2⌉)+1的解为O(lgn)。
页:
[1]