# 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. – gnasher729 Mar 11 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). – gnasher729 Mar 11 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 = 1: True because T(2) = 1.

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.

• Thanks, your solution is what I am looking for. – Sophie Roseinsta Mar 11 at 14:57

I think you can just use the Master theorem:

Theorem: For $$a$$, $$b$$ $$\in$$ $$\mathbb{N}$$, $$b > 1$$ and a function $$g : \mathbb{N} \rightarrow \mathbb{N}$$ with $$g \in \Theta(n^c)$$, the recurrence equation shall have the form: $$T(1) = g(1)$$ $$T(n) = a · T\left(\frac{n}{b}\right) + g(n)$$

Then it holds true that: $$T(n) \in \Theta(n^c )\ \text{ if } a < b^c$$ $$T(n) \in \Theta(n^c \log(n))\ if\ a = b^c$$ $$T(n) \in \Theta\left(n^{\frac{\log(a)}{\log(b)}}\right) \ if\ a > b^c$$

In your case, $$a = 1, b = 2, c = 0$$ and $$a = b^c$$. So $$T(n)$$ $$\in$$ $$\Theta(\log(n))$$ which is also in $$\mathcal{O}(\log(n))$$

• Thanks for the suggestion, unfortunately I am not allowed to use the master theorem for this exercise. But still thanks. – Sophie Roseinsta Mar 11 at 12:39
• You're welcome :D – Hsssdksasd kalskmdsma Mar 11 at 12:40