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

• Obviously there is no solution because you expect T(1) = T(1)+1 and T(0)=T(0)+1. Mar 11, 2021 at 14:29
• Prove instead: For all k >= 0: T(n) <= c*k + d for all n <= 2^k. Your approach going from n to n+1 cannot work because for example T(1025) is a lot bigger than T(1024). Mar 11, 2021 at 14:34

If you let T(0) = T(1) = 0, then prove by complete induction for every k >= 1 that T(n) = k for all n such that $$2^{k-1} < n <= 2^k$$.
k -> k + 1: Let $$2^k < n <= 2^{k+1}$$. Then $$2^{k-1} < n/2 <= 2^k$$, therefore $$2^{k-1} < \lceil n/2 \rceil<= 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 >= 1.