1
$\begingroup$

I have this given recurrence relation:

$T(n) = 3T(\lfloor n/2 \rfloor)$

Initial value: $T(1) = 1$

and I should show that $T(n) = O(n^{\alpha})$ and $\alpha = log_2(3)$

to solve that I should define: $P(n) :\Leftrightarrow T(n) \leq n^{\alpha}$ and $P(n)$ holds for all $n \geq 1$ and I should show that by induction.

But I don't understand what that $P(n) :\Leftrightarrow T(n) \leq n^{\alpha}$ means?

Is $P(n) = T(n)$?


solution:

Base:

$n \geq 1$ and $n = 1$

$$3T(\lfloor 1/2 \rfloor) \leq 1^{log_2(3)}$$

$$\lfloor 3/2 \rfloor \leq 1^{log_2(3)}$$

$$1 \leq 1$$

Hypothesis:

$$3T(\lfloor n/2 \rfloor) \leq n^{log_2(3)}$$

Step:

$T(n) = 3T(\lfloor \frac{n}{2} \rfloor) \\ \leq (\frac{n}{2})^{log_2(3)} \\ = 3^{log_2(\frac{n}{2})} \\ = 3^{log_2(n)- log_2(2)} \\ = 3^{log_2(n)- 1} \\ \leq 3^{log_2(n)} = n^{log_2(3)} $

is that right?

$\endgroup$
4
  • $\begingroup$ $P(n)$ is not a function but $T(n)$ is, $P(n)$ is a proposition. $\endgroup$
    – Tuvasbien
    Dec 27 '19 at 16:15
  • $\begingroup$ ok but how should I define P(n)? Is it not possible to do the induction on T(n)? $\endgroup$ Dec 27 '19 at 16:17
  • 1
    $\begingroup$ I don't think it is the best way to prove it, moreover $T(n)=\mathcal{O}(n^{\alpha})$ doesn't mean that $T(n)\leqslant n^{\alpha}$, it means that there exists $C>0$ such that $T(n)\leqslant C n^{\alpha}$ for all $n\in\mathbb{N}$. I would suggest to study $u_p=T(2^p)$ that verifies $u_{p+1}=3u_p$, show by induction that $T$ is increasing, then use $T(n)\leqslant u_{1+\lfloor \log_2(n)\rfloor}$. $\endgroup$
    – Tuvasbien
    Dec 27 '19 at 16:23
  • $\begingroup$ ok thanks I think now I get it $\endgroup$ Dec 27 '19 at 16:25
1
$\begingroup$

Prove, by induction on the number of binary digits of $n$, that $T(n)=3^{\lfloor\log_2n\rfloor}$. Since $3^{\log_2n}=n^{\log_23}$, $\frac13n^{\log_23}\lt T(n)\le n^{\log_23}$.

$\endgroup$
4
  • $\begingroup$ why ist T(n) =3 ^⌊log2n⌋? $\endgroup$ Dec 27 '19 at 20:46
  • $\begingroup$ @ArminZierlinger For $j\in\{0,\,1\}$, $T(2n+j)=3T(n)$. Apart from the factor of $3$, we've deleted the last binary digit of $T$'s argument. Now repeat. The first such digit is $1$. $\endgroup$
    – J.G.
    Dec 27 '19 at 20:49
  • $\begingroup$ is that now right? $\endgroup$ Dec 28 '19 at 1:15
  • $\begingroup$ @ArminZierlinger No. $\endgroup$
    – J.G.
    Dec 28 '19 at 7:31

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.