Prove $T(n) = T(\left \lceil{\frac{n}{2}}\right \rceil) + 1 = O(\log(n))$ As the title said, prove $T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1 = O(\log(n))$
My approach is to find $c, n_0 \in \mathbb{R}_+$ such that:
$$\forall n \geq n_0, T(n) \leq c\log(n) -d \text{, where d is a constant}$$
Assume the statement is true for every $m &lt; n$, especially $m = \left\lceil{\frac{n}{2}}\right\rceil$, therefore
$$T(\left\lceil{\frac{n}{2}}\right\rceil) \leq c \log(\left\lceil{\frac{n}{2}}\right\rceil) - d $$
$$\iff T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1$$
$$\leq c\log(\left\lceil{\frac{n}{2}}\right\rceil) - d + 1$$
$$= c\log(\left\lfloor{\frac{n}{2}}\right\rfloor + 1) - d + 1$$
$$\leq c\log(\frac{n + 2}{2}) - d + 1$$
$$= c\log(n + 2) - c\log(2) - d + 1$$
$$= c\log(n + 2) - d$$
This is where I stuck and can not go further. I need to eliminate the constant $2$ in $n + 2$. Any help and hint is welcome.
Edit: In term of master theorem. I have to solve this recurrence with substitution method.
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.