postać jawna

[monpor7]

Znajdz postac jawną oraz udowodnij ją przez indukcję:
\(T(n)=3T(\lfloor\frac{n}{2}\rfloor)\)
\(T(1)=2\)

Oraz z postaci jawnej wydedukuj
\(T(n)=0(n^{log_2 3})\)

[octahedron]

\(T(2)=3T\(\lfloor 1\rfloor\)=3T(1)
T(3)=3T\(\lfloor 1\frac{1}{2}\rfloor\)=3T(1)
T(4)=3T\(\lfloor 2\rfloor\)=3T(2)=3^2T(1)
T(5)=3T\(\lfloor 2\frac{1}{2}\rfloor\)=3T(2)=3^2T(1)
T(6)=3T\(\lfloor 3\rfloor\)=3T(3)=3^2T(1)
T(7)=3T\(\lfloor 3\frac{1}{2}\rfloor\)=3T(3)=3^2T(1)
T(8)=3T\(\lfloor 4\rfloor\)=3T(4)=3^3T(1)=T(9)=...=T(15)
T(16)=...=T(31)=3^4T(1)
itd...
T(n)=2\cdot 3^{\lfloor \log_2n\rfloor}
3^{\lfloor \log_2n\rfloor}\le 3^{\log_2n}
\log_33^{\log_2n}=\log_2n
\log_3n^{\log_23}=\log_23\cdot\log_3n=\log_2n \Rightarrow 3^{\log_2n}=n^{\log_23}
T(n)\le 2\cdot n^{\log_23} \Rightarrow T(n)=O\(n^{\log_23}\)\)