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}\]