Exercise 4.3.2

Show that the solution of T(n)=T(n/2)+1T(n) = T(\lceil n/2 \rceil) + 1 is O(lgn)O(\lg{n})

We guess T(n)clg(n2)T(n) \le c\lg(n - 2):

T(n)clg(n/22)+1clg(n/2+12)+1clg((n2)/2)+1clg(n2)clg2+1clg(n2) T(n) \le c\lg(\lceil n/2 \rceil - 2) + 1 \le c\lg(n/2 + 1 - 2) + 1 \le c\lg((n - 2)/2) + 1 \le c\lg(n - 2) - c\lg2 + 1 \le c\lg(n - 2)