Exercise 4.3.2 Show that the solution of T(n)=T(⌈n/2⌉)+1T(n) = T(\lceil n/2 \rceil) + 1T(n)=T(⌈n/2⌉)+1 is O(lgn)O(\lg{n})O(lgn) We guess T(n)≤clg(n−2)T(n) \le c\lg(n - 2)T(n)≤clg(n−2): T(n)≤clg(⌈n/2⌉−2)+1≤clg(n/2+1−2)+1≤clg((n−2)/2)+1≤clg(n−2)−clg2+1≤clg(n−2) 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) T(n)≤clg(⌈n/2⌉−2)+1≤clg(n/2+1−2)+1≤clg((n−2)/2)+1≤clg(n−2)−clg2+1≤clg(n−2)