算法导论习题解答 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)。

?