Jaka jest złożoność obliczeniowa w najgorszym przypadku (ang. worst-case) dla klasycznego, nieoptymalizowanego algorytmu sortowania bąbelkowego (Bubble Sort) przetwarzającego tablicę o rozmiarze n elementów?

Poprawna odpowiedź: C (O(n²))

Ponieważ w najgorszym scenariuszu (gdy elementy wejściowe są poukładane w odwrotnej kolejności do pożądanej) nieoptymalizowany algorytm bąbelkowy musi porównać każdy element z każdym innym za pomocą dwóch zagnieżdżonych pętli, co skutkuje wykonaniem operacji proporcjonalnie do kwadratu liczby elementów, czyli O(n^2).

Opcja A reprezentuje optymistyczną złożoność czasową niektórych zoptymalizowanych algorytmów (np. sortowania bąbelkowego z flagą zmiany dla już posortowanej tablicy). Opcja B określa złożoność najwydajniejszych algorytmów sortowania przez porównanie, takich jak Merge Sort czy Heap Sort. Opcja D określa złożoność wykładniczą, charakterystyczną dla skomplikowanych problemów o charakterze kombinatorycznym.

Dlaczego pozostałe opcje są nieprawidłowe?

• A: Opcja O(n) nie odpowiada prawidłowemu rozwiązaniu problemu opisanego w pytaniu.
• B: Opcja O(n log n) nie odpowiada prawidłowemu rozwiązaniu problemu opisanego w pytaniu.
• D: Opcja O(2ⁿ) nie odpowiada prawidłowemu rozwiązaniu problemu opisanego w pytaniu.