Cześć,
Poniżej przedstawię treść jak i rozwiązanie pewnego zadania.Chciałbym aby ktoś z wiedzą utwierdził mnie w przekonaniu, że zrobiłem je dobrze(lub tez nie , a wtedy pomógł z problemem).
Treść zadania: Określ złożoność czasową algorytmu rekurencyjnego dla którego zachodzi następująca zależność:
\(\displaystyle{ T \left( n \right) = \begin{cases} \theta \left( 1 \right) , n=1 \\ 2T \left( \frac{n}{2} \right) +\theta \left( \log n \right) ,n>1 \end{cases}}\)
Rozwianie:
Jeżeli wiem, że \(\displaystyle{ f \left( n \right)}\) ma złożoność \(\displaystyle{ \theta \left( \log n \right)}\) to tym bardziej \(\displaystyle{ f \left( n \right) =O \left( n^{1-k} \right)}\) dla \(\displaystyle{ k=0.5}\).
Z tw. o rekurencji u. \(\displaystyle{ T \left( n \right) =\theta \left( n \right)}\).
Logarytmów nie piszę bo w tym przypadku mamy logarytm o podstawie 2 z 2 czyli jeden.
Dla mnie to ma sens ale widziałem różne wyniki tego zadania dlatego pytam.
