Show that the solution of \(T(n) = T(\lceil n / 2 \rceil) + 1\) is \(O(\lg n)\).
Let us assume \(T(n) \le c \lg n\) for all \(n \ge n_0\), where \(c\) and \(n_0\) are positive constants.
\[\begin {aligned} T(n) & \le c \lg \left \lceil \frac n 2 \right \rceil + 1 \\ & < c \lg \left( \frac n 2 + 1 \right) + 1 \\ & < c \lg \left( \frac {n + 2} 2 \right) + 1 \\ & = c \lg (n + 2) - c \lg 2 + 1 \\ & = c \lg (n + 2) - c + 1 \end {aligned}\]This is inconclusive, as we cannot arrive at our assumption from the last step. So we’ll modify our assumption a bit by subtracting a lower-order term from our previous guess.
Let us assume \(T(n) \le c \lg (n - 2)\).
\[\begin {aligned} T(n) & \le c \lg \left \lceil \frac n 2 - 2\right \rceil + 1 \\ & < c \lg \left( \frac n 2 - 2 + 1 \right) + 1 \\ & < c \lg \left( \frac {n - 2} 2 \right) + 1 \\ & = c \lg (n - 2) - c \lg 2 + 1 \\ & = c \lg (n - 2) - (c - 1) \\ & \le c \lg (n - 2) \end {aligned}\]The last step holds as long as \(c \ge 1\).