Help with problem 4.1-1 from CLRS 2nd edition The exercise says &quot;Show that the solution of $T(n) = T(\lceil{n/2}\rceil) + 1$ is $O(\lg(n))$.&quot; I came up with a solution for this exercise using the substitution method but I don't know if it is correct. My solution goes like this: I claim $T(n) \leq c\lg{n}$ and assume it holds for $\lceil{n/2}\rceil$, then
$$
\begin{aligned}
T(n) &amp;\le c\lg(\lceil{n/2}\rceil) + 1 &amp;&amp; \text{Inductive Hypothesis}\\
&amp;= c\lg(n/2) + 1 &amp;&amp; \text{Omitting ceiling}\\
&amp;= c\lg{n} - c + 1 &amp;&amp; \text{Algebra}\\
&amp;\le c\lg{n} &amp;&amp; \text{for $c\ge1$}
\end{aligned}
$$
I omit the ceiling function according to the text.
I, however, found another solution on the internet that is slightly more complicated which makes me think my solution is probably wrong. It states that $T(n) \leq c\lg(n - b)$ and assumes it holds for $\lceil{n/2}\rceil$, consequently:
$$
\begin{aligned}
T(n) &amp;\le c\lg({\lceil{n/2-b}\rceil}) + 1 \\
&amp;\lt c\lg(n/2-b + 1) + 1\\
&amp;= c\lg\big(\frac{n-2b+2}{2}\big) + 1\\
&amp;= c\lg(n-2b+2) - c\lg2 + 1\\
&amp;\le c\lg(n - b)
\end{aligned}
$$
Where the last inequality requires that $b \ge 2$ and $c \ge 1$.
My question is if my solution is correct, then why subtract $b$ from $n$ in the second solution? If my solution is not correct, is subtracting $b$ from $n$ absolutely necessary and why is my solution not correct?
As pointed out in the comments, your proof is wrong since it is not true in general that $\log \lceil n/2 \rceil \leq \log n/2$. For example, if $n = 1$ then the left-hand side is zero while the right-hand side is negative.

In the comment you mention that the text states that they omit floors and ceilings. This is always wrong. You cannot &quot;omit&quot; stuff. It invalidates your entire reasoning. (Sometimes, however, you can use true inequalities to get rid of floors or ceilings: for example, $\lfloor x \rfloor \leq x$.)
Consider for example a divide-and-conquer algorithm which splits its input into two halves and performs some $O(n)$ processing. You often see its running time expressed as the recurrence
$$ T(n) = 2T(n/2) + O(n). $$
This is clearly wrong – what if $n$ is odd? What does $T(13.5)$ even mean? The argument has to be a positive integer! The real recurrence is probably more like
$$
T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n).
$$
When the text states that they omit floors and ceilings, they are being sloppy. They allow themselves to do that since you can solve the true recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$ via the fake one $T(n) = 2T(n/2) + O(n)$, which should be interpreted as defining a function $T(n)$ for all positive values of $n$.
You can see this sentiment expressed formally in the Akra–Bazzi theorem, where floors and ceilings don't change the answer. Another way to see it is to consider only values of $n$ of the form $n = 2^m$. For these values, the recurrence $T(n) = 2T(n/2) + O(n)$ does hold. You can prove by induction that the solution to the recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$, and so it suffices (in this case) to determine the asymptotic rate of growth for $n$ of the form $n = 2^m$.

How do you solve your recurrence, $T(n) = T(\lceil n/2 \rceil) + 1$? First of all, you have to supply some base case, say $T(1) = C$. Given $n$, we now construct the following sequence: $n_0 = n$, $n_{i+1} = \lceil n_i/2 \rceil$. You can check that $T(n)$ equals $C$ plus the minimal index $i$ such that $n_i = 1$.
Since $\lceil m/2 \rceil \leq (m+1)/2$, we know that $n_1 \leq (n+1)/2$, and so $n_2 \leq (n+3)/4$, and $n_3 \leq (n+7)/8$, and so on. More generally, $n_i \leq (n+2^i-1)/2^i &lt; n/2^i + 1$. Hence if $i = \lceil \log_2 n \rceil$ then $n_i &lt; n/n + 1 = 2$, implying that $n_i \leq 1$.
In the other direction, clearly $n_i \geq n/2^i$, and so if $i = \lceil \log_2 n \rceil - 1 &lt; \log_2 n$ then $n_i &gt; 1$, implying that $T(n) &gt; \lceil \log_2 n \rceil - 1 + C$.
We conclude that the minimal $i$ such that $n_i = 1$ is exactly $\lceil \log_2 n \rceil$. Hence $T(n) = C + \lceil \log_2 n \rceil$.