Matematyka dyskretna 1/Ćwiczenia 9: Asymptotyka

Z Studia Informatyczne
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