Metoda rekursji uniwersalnej - bardzo prosty przykład

[freak91]

Mam następujący przykład:
\(\displaystyle{ T \left( n \right) =2T \left( \frac{n}{2} \right) +1}\)

Stosuje twierdzenie:
Niech \(\displaystyle{ a \ge 1}\), \(\displaystyle{ b>1}\). Załóżmy, że
\(\displaystyle{ T \left( n \right) =aT \left( \frac{n}{b} \right) +f \left( n \right)}\),
gdzie\(\displaystyle{ f: N o left[ 0, infty
ight)}\), \(\displaystyle{ T \left( 1 \right) = \Theta \left( 1 \right)}\) i \(\displaystyle{ \frac{n}{b}}\) może oznaczać \(\displaystyle{ \lfloor \frac{n}{b} \rfloor}\) lub \(\displaystyle{ \lceil \frac{n}{b} \rceil}\).
Wówczas:
(a) jeżeli \(\displaystyle{ \bigvee_{ \epsilon >0}f \left( n \right) =O \left( n^{\log _ba- \epsilon} \right)}\), to \(\displaystyle{ T \left( n \right) = \Theta \left( n^{\log _ba} \right)}\),
(b) jeżeli \(\displaystyle{ f \left( n \right) = \Theta \left( n^{\log _ba} \right) , to T \left( n \right) = \Theta \left( n^{\log _ba}\lg n \right)}\),
(c) jeżeli \(\displaystyle{ \bigvee_{ \epsilon >0}f \left( n \right) = \Omega \left( n^{\log _ba+ \epsilon} \right)}\) oraz \(\displaystyle{ \bigvee _{c_1<1} \bigvee _{n_0 \in N} \bigwedge _{n \ge n_0} af \left( \frac{n}{b} \right) \le cf \left( n \right)}\) , to \(\displaystyle{ T \left( n \right) = \Theta \left( f \left( n \right) \right)}\)

Odczytuje, że:
\(\displaystyle{ a = 2}\)
\(\displaystyle{ b = 2}\)
\(\displaystyle{ f \left( n \right) = 1}\)
\(\displaystyle{ \log _{b}{a} = 1}\)

Prawdą jest, że:
\(\displaystyle{ f \left( n \right) < n^{\log _{b}{a}}}\)
\(\displaystyle{ 1 < n}\)
Będzie to 3 przypadek twierzenia.

Wniosek jest następujący:
\(\displaystyle{ T \left( n \right) =\Theta \left( f \left( n \right) \right) =\Theta \left( 1 \right)}\)

Czy jest to prawda?

[Qń]

Jesteś pewien, że wiesz co oznacza notacja \(\displaystyle{ \Omega}\)?

Q.

[freak91]

Powiedzmy, że tak, ale na daną chwilę jest to dla mnie dość zagmatwane. Notacja \(\displaystyle{ \Omega}\) oznacza oszacowanie funkcji od dołu. O od góry, a \(\displaystyle{ \Theta}\) dokładne.

[Qń]

Dlaczego więc twierdzisz, że jedynkę da się oszacować z dołu przez \(\displaystyle{ n^{1+\varepsilon}}\)?

Q.

[freak91]

Powiedziałbym, że raczej \(\displaystyle{ n^{1 - \epsilon}}\). Jednocześnie przepraszam za głupie pytania, bo staram się to zrozumieć, a idzie trochę jak krew z nosa.

[Qń]

Moment. Mamy do wyboru trzy sytuacje:
a) jedynkę da się oszacować z góry przez \(\displaystyle{ n^{1-\varepsilon}}\)
b) jedynka jest dokładnie rzędu \(\displaystyle{ n}\)
c) jedynkę da się oszacować z dołu przez \(\displaystyle{ n^{1+\varepsilon}}\)

W pierwszym poście napisałeś, że zachodzi możliwość c). Dlaczego?

Q.

[freak91]

Znalazłem fałszywą zależność (dla f(n) z pominięciem stałej):
Jeżeli \(\displaystyle{ f(n) > n^{log_b{a}}}\) to zachodzi przypadek 1.
Jeżeli \(\displaystyle{ f(n) = n^{log_b{a}}}\) to zachodzi przypadek 2.
Jeżeli \(\displaystyle{ f(n) < n^{log_b{a}}}\) to zachodzi przypadek 3.

Chyba nie ma to sensu.

[Qń]

Nie rozumiem co próbujesz powiedzieć. Jeśli to, że źle przytoczyłeś treść twierdzenia, to nie, treść jest ok. A jeśli coś innego to nie wiem co.

Q.

[freak91]

Czyli jest to prawda:
Jeżeli \(\displaystyle{ f(n) > n^{log_b{a}}}\) to zachodzi przypadek 1.
Jeżeli \(\displaystyle{ f(n) = n^{log_b{a}}}\) to zachodzi przypadek 2.
Jeżeli \(\displaystyle{ f(n) < n^{log_b{a}}}\) to zachodzi przypadek 3.
Ok. To na podstawie tego stwierdziłem, że wychodzi przypadek 3. Jak stwierdziłem jaki przypadek wychodzi, to uznałem, że muszę podać odpowiedź:
\(\displaystyle{ T(n)= \Theta (f(n))}\)
Chyba nie jest to tym samym f(n) co poprzednie.

[Qń]

Nie, pisząc o treści twierdzenia miałem na myśli pierwszy post z tego wątku. A jaki związek z tym twierdzeniem ma to co piszesz teraz - nie wiem. Przedstawiłem trzy możliwe sytuacje - co jest w tym dla Ciebie niejasnego?

Q.