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?
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}$.