Porownanie oszacowan asymptotycznych

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
UnknownSoldier
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 10 gru 2019, o 00:09
Płeć: Mężczyzna
wiek: 21
Podziękował: 3 razy

Porownanie oszacowan asymptotycznych

Post autor: UnknownSoldier » 20 sty 2020, o 23:57

Korzystajac z tw. o rekurencji uniwersalnej wyznacz asymptotycznie dokladne oszacowanie rozwiazania ponizszych rekurencji
a) \(\displaystyle{ T\left( n \right) = 8T\left( \frac{n}{2} \right) + 7n^{4}+1 }\)
b) \(\displaystyle{ T\left( n \right) = 27T\left( \frac{n}{3} \right) + 2n^{3} + (n \cdot lgn)^{2} }\)
Dokonaj porownania otrzymanych w a) i b) oszacowan.

W a wychodzi mi \(\displaystyle{ T\left( n \right) = \Theta\left( 7n^{4} + 1\right)}\)
natomiast w b \(\displaystyle{ T\left( n \right) = \Theta\left( n^{3} \cdot lgn \right)}\)

czy moglby ktos powiedziec na jakiej zasadzie mozna porownac oszacowania?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

ODPOWIEDZ