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$ – Sophie Roseinsta Mar 11 at 14:57
0
$\begingroup$

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))$

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

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.