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$$.