算法导论习题解答 4.1-1

amazingidiot

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)。