[Algorytmy] Oszacowanie górne

[nwnuinr]

Cześć

mam takie zadanko: Wyznacz asymptotyczne oszacowanie górne dla rekurencji \(\displaystyle{ T(n)=2T(\sqrt{n})+1}\)

No i ja to rozwiązałem w taki sposób, ale nie jestem pewien czy jest ok.

(Gdyby ktoś potrzebował definicji na oszacowanie górne):
\(\displaystyle{ f(n)=O(g(n)) \Rightarrow \exists _{c>0,n_{0}>0} \forall _{n \ge n_{0}} 0 \le f(n) \le c \cdot g(n)}\)

\(\displaystyle{ m=\sqrt{n} \\ n=m^{2} \\ T(m^{2})=2T(m)+1 \\ S(m)=T(m^{2}) \\ S(m)=2S(m)+1=O(2^{m+1}-1)=O(2^{m})=O(2^{\sqrt{n}})}\)

Pozdrawiam i dzięki z góry za pomoc.

[paladin]

Cześć

(...)

\(\displaystyle{ T(m^{2})=2T(m)+1 \\ S(m)=T(m^{2}) \\ S(m)=2S(m)+1= \ldots}\)

Obawiam się, że w tym miejscu źle wstawiłeś.
Rozwiązanie tej rekursji jest inne. Wstaw \(\displaystyle{ n = 2^k}\).