twierdzenie o rekurencji uniwersalnej.

[tukanik]

Cześć
Wiadomo, że twierdzenie to rozważa trzy przypadki, jednym z nich jest:
1. Jeżeli\(\displaystyle{ f(n) = O(n^{\log_b^{a}-\epsilon} )}\)dla pewnego stałego, dodatniego epsilon, wtedy \(\displaystyle{ T(n) = \Theta(n^{\log_b^a})}\)
Dlaczego jeżeli pokażemy, że \(\displaystyle{ n^{\log_b^{a}-\epsilon}}\) ogranicza z góry nasze rozwiązanie to możemy już stwierdzić, że jest to też dobre ograniczenie dolne?

[bartek118]

A jak wygląda rekurencja?

[tukanik]

możesz jaśniej?

[PiotrowskiW]

Dlaczego jeżeli pokażemy, że n^{log_b^{a}-epsilon} ogranicza z góry nasze rozwiązanie to możemy już stwierdzić, że jest to też dobre ograniczenie dolne?

Rozumiem, że chodzi ci o tego samego epsilona z góry i z dołu?
Tak nie jest w większości przypadków.Gdy tak jest to mamy po prostu równość.

[tukanik]

Jeszcze raz:
Mamy równanie rekurencyjne takiej postaci:
\(\displaystyle{ T \left( n \right) = aT \left( \frac{n}{b} \right) + f \left( n \right)}\)
Teraz szukając rozwiązania chcicałbym zastosować twierdzenie o rekurencji uniwersalnej.
Jak wiadomo, rozważa ono 3 przypadki. Pierwszym z nich jest:
1. Jeżeli \(\displaystyle{ f \left( n \right) = O \left( n^{\log_ba-\epsilon } \right)}\)dla pewnego dodatniego stałego \(\displaystyle{ \epsilon}\) to \(\displaystyle{ T \left( n \right) =\Theta \left( n^{\log_ba } \right)}\)
Załóżmy, że warunek zachodzi. Ja się teraz pytam, dlaczego niby pokazanie ograniczenia górnego dla \(\displaystyle{ f \left( n \right)}\)daje nam dokładne ograniczenie dla całej rekuencji?