Matematyka dyskretna 1/Ćwiczenia 9: Asymptotyka

Z Studia Informatyczne
< Matematyka dyskretna 1
Wersja z dnia 13:30, 5 cze 2020 autorstwa Luki (dyskusja | edycje) (→‎Asymptotyka)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Asymptotyka

Ćwiczenie 1

Posortuj podane niżej funkcje według asymptotycznego stopnia złożoności tak, by każda funkcja była asymptotycznie niemniejsza od następujących po niej.



Wskazówka

Ćwiczenie 2

Oszacuj rząd wielkości funkcji zadanej równaniem rekurencyjnym:

Wskazówka
Rozwiązanie

Ćwiczenie 3

Oszacuj rząd wielkości funkcji zadanej równaniem rekurencyjnym:

Wskazówka
Rozwiązanie

Ćwiczenie 4

Oszacuj rząd wielkości funkcji zadanej równaniem rekurencyjnym:

Wskazówka
Rozwiązanie

Ćwiczenie 5

Oszacuj rząd wielkości funkcji zadanej równaniem rekurencyjnym:

Wskazówka
Rozwiązanie

Ćwiczenie 6

Oszacuj rząd wielkości funkcji zadanej równaniem rekurencyjnym:

Wskazówka
Rozwiązanie

Ćwiczenie 7

Dla



wskaż największą całkowitą wartość parametru taką, że .

Wskazówka
Rozwiązanie

Ćwiczenie 8

Udowodnij przez indukcję, że dla zachodzi:



Wskazówka
Rozwiązanie