Zadanie 1.

Niech
opisuje złożoność pewnego algorytmu. Jeżeli ten algorytm wykonuje zadanie X o rozmiarze 6 w czasie 18 sekund na komputerze K, to ile czasu potrzebuje na wykonanie zadania Y, trzy razy większego niż zadanie X, także na komputerze K?

Złożoność algorytmu dla danych rozmiaru n określona jest przez funkcję
. Dla zadania X rozmiaru 6 algorytm ten wykona
operacji dominujących. Czas potrzebny do wykonania tego zadania na komputerze K wynosi 18 sekund. Zatem wykonanie pojedynczej operacji dominującej zajmuje
sekundy. Dla zadania Y rozmiaru
rozważany algorytm wymaga wykonania dokładnie
operacji dominujących. Komputer K upora się z tym zadaniem w ciągu
sekund.

Zadanie 2.

Na komputerze K wykonanie algorytmu A dla danych o rozmiarze 6 zajmuje 8 sekund. Złożoność tego algorytmu opisuje funkcja
.

Ile czasu będzie potrzebował komputer K1, dokładnie 1024 razy szybszy od komputera K, do wykonania algorytmu A dla danych rozmiaru 20?

sekund

Zadanie 3.

Niech
opisuje złożoność pewnego algorytmu. Jeżeli ten algorytm wykonuje zadanie X o rozmiarze 6 w czasie 18 sekund na komputerze K.

Ile czasu zajmie wykonanie zadania Y (trzy razy większego niż X) na komputerze K1, dziesięć razy wolniejszym niż komputer K?

Czas wykonania pojedynczej operacji dominującej na komputerze K wynosi
sekundy. Komputer K1 dziesięć razy wolniejszy od K potrzebuje na wykonanie tego samego zadania dokładnie
sekundy. Zatem zadanie Y wymagające 5832 operacji dominujących zostanie zakończone na komputerze K1 po
sekundach.

Zadanie 4.

Podaj możliwie najlepsze oszacowanie następującej funkcji stosując notację O:

Funkcja	Oszacowanie

Zadanie 5.

Podaj możliwie proste oszacowanie następującej funkcji stosując notację Θ:

Funkcja	Oszacowanie

---