Analiza złożoności Niech oznacza złożoność czasową algorytmu. Zauważmy, że wykonanie algorytmu składa się z trzech kroków znajdowania median piątek, wykonywanego w czasie wybierania (rekurencyjnie) mediany zbioru wykonywanego w czasie wykonania wywołania rekurencyjnego, wykonywanego co najwyżej w czasie
Jak wcześniej zauważyliśmy zatem szacując czas wykonania całego algorytmu przez sumę maksymalnych czasów wykonań kroków, dostajemy nierówność
Stosując standardowe metody rozwiązywania nierówności asymptotycznych (kluczowe jest, że ) dostajemy, że algorytm magicznych piątek nawet pesymistycznie jest liniowy.
Bibliografia
Kategoria:Algorytmy