Show that the upper bound and the lower bound for the recurrence

T$($n$)=$ T$($n$/2)+1$ are O$($lg n$)$ and pi$($lg n$),$ respectively