1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Obviously there is no solution because you expect T(1) = T(1)+1 and T(0)=T(0)+1. $\endgroup$
    – gnasher729
    Mar 11 at 14:29
  • $\begingroup$ 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). $\endgroup$
    – gnasher729
    Mar 11 at 14:34
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, your solution is what I am looking for. $\endgroup$ Mar 11 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.