kiedy musimy rozwiązać problem i gdy dostępnych jest wiele sposobów rozwiązania tego problemu (na przykład problem mnożenia łańcucha macierzy), w tym czasie potrzebna jest analiza algorytmu.

analiza algorytmów oznacza oszacowanie ich złożoności w sensie asymptotycznym. Termin „analiza algorytmów” został ukuty przez Donalda Knutha. Analiza algorytmów to określenie ilości zasobów czasu i przestrzeni potrzebnych do jej wykonania.

większość algorytmów ma charakter rekurencyjny, używają strategii dziel i rządź. Algorytm rekurencyjny wywołuje się dla innych wejść. Zwykle jest to część oryginalnego wejścia, ale ma mniejszy rozmiar (problem podrzędny). Istnieje wiele sposobów rozwiązania relacji powtarzania. Są one następujące:

1. Twierdzenie mistrza

2. Metoda drzewa nawrotów

3. Metoda substytucji

4. Zmiana metody zmiennej

spośród wszystkich tych metod twierdzenie mistrza jest najszybszą metodą znajdowania złożoności czasowej funkcji. Jest bardzo łatwy do zrozumienia i łatwy do zastosowania. Musimy tylko pamiętać o niektórych sprawach. Zaczynamy.