Złożoność pesymistyczna
Złożoność pesymistyczna określa złożoność w „najgorszym” przypadku. Jeśli oznacza zbiór wszystkich możliwych danych wejściowych, jeden z elementów tego zbioru, a funkcję, która dla danego zwraca liczbę operacji, to złożoność pesymistyczna jest zdefiniowana jako: [1].
Pesymistyczna złożoność czasowa, oznaczana W() (od ang. “worst”) to funkcja wyrażająca kres górny możliwej liczby operacji dominujących dla ustalonego rozmiaru danych (wariant pesymistyczny). Wyraża liczbę wykonanych operacji dominujących w najgorszym (pesymistycznym) przypadku[1].
W przypadku złożoności obliczeniowej algorytmu złożoność pesymistyczna O() jest ilością zasobów (np. czasu lub dodatkowej pamięci) potrzebnych do wykonania algorytmu przy założeniu najbardziej złośliwych lub najgorszych danych[2][3].