Prove $T(n) = T(\left \lceil{\frac{n}{2}}\right \rceil) + 1 = O(\log(n))$
If you let T(0) = T(1) = 0, then prove by complete induction for every k &gt;= 1 that T(n) = k for all n such that $2^{k-1} &lt; n &lt;= 2^k$.
k = 1: True because T(2) = 1.
k -&gt; k + 1: Let $2^k &lt; n &lt;= 2^{k+1}$. Then $2^{k-1} &lt; n/2 &lt;= 2^k$, therefore $2^{k-1} &lt; \lceil n/2 \rceil&lt;= 2^k$, therefore $T(\lceil n/2 \rceil) = k$, therefore T(n) = k+1.
So instead of O(log n) you get the much stronger $T(1) + \lceil \log_2 n \rceil$ for all n &gt;= 1.