Show that the solution of \(T(n) = T(\lceil n/2 \rceil) + n\) is \(O(\lg n)\).

In order to use the substitution method, we guess that the solution is \(O(\lg n)\) and must prove that \(T(n) \leq c \lg n\) for some \(c > 0\). We assume that this bound holds for all positive \(m < n\) such as \(m = \lceil n/2 \rceil\) (for sufficient values of \(n\)):

\[T(\lceil n/2 \rceil) \leq c \lg( \lceil n/2 \rceil) + 1\]

Substituting into the recurrence yields

\[\begin{split} T(n) & \leq c \lg (\lceil n/2 \rceil) + 1 \\ & = c \lg \left( \frac{n}{2} + 1 \right) + 1 \\ & = c \lg \left( \frac{n + 2}{2} \right) + 1 \\ & = c(\lg ( n + 2) - \lg(2)) + 1 \\ & = c\lg(n+2) - c + 1 \\ & \leq \lg n \end{split}\]

Unfortunately, there are no values of \(c\) for which the last step holds. Given the form of our final step, let us modify our original guess slightly to be \(T(n) \leq c \lg(n-d)\) for some constant \(d\). We make the same assumption that this bound holds for all positive \(m < n\) such as \(m = \lceil n/2 \rceil\) (for sufficient values of \(n\)):

\[T(\lceil n/2 \rceil) \leq c \lg( \lceil n/2 \rceil - d) + 1\]

Substituting into the recurrence yields

\[\begin{split} T(n) & \leq c \lg (\lceil n/2 \rceil - d) + 1 \\ & = c \lg \left( \frac{n}{2} - d + 1 \right) + 1 \\ & = c \lg \left( \frac{n -2d + 2}{2} \right) + 1 \\ & = c(\lg ( n -2d + 2) - \lg(2)) + 1 \ \ \ ( \text{let} \ d = 2 ) \\ & = c\lg(n - 2) - c + 1 \ \ \ ( \text{let} \ c = 1 ) \\ & = \lg(n - 2) \\ & \leq \lg n \end{split}\]

This last step holds for \(c = 1\), \(d = 2\) and all \(n > 2\).