Dla podanego algorytmu złożoność obliczeniowa jest równa

Poprawna odpowiedź: B

Uzasadnienie i szersze wyjaśnienie:

Przedstawiony algorytm to wyszukiwanie liniowe (sekwencyjne). Jego działanie polega na przechodzeniu przez tablicę element po elemencie (krok K4: i <- i + 1) i porównywaniu każdego z nich z szukaną wartością x.

Złożoność obliczeniowa opisuje, jak czas wykonania algorytmu zależy od rozmiaru danych wejściowych, w tym przypadku od liczby elementów w tablicy, czyli n. W najgorszym przypadku (gdy szukany element znajduje się na końcu tablicy lub w ogóle go w niej nie ma), algorytm musi przejrzeć wszystkie n elementów. Oznacza to, że liczba operacji jest wprost proporcjonalna do n, co w notacji Wielkiego O zapisujemy jako O(n).

Dlaczego pozostałe odpowiedzi są nieprawidłowe?

• A. O(n log n): Jest to złożoność typowa dla wydajnych algorytmów sortowania, takich jak sortowanie przez scalanie.
• C. O(1): Złożoność stała; oznaczałaby, że czas wykonania nie zależy od rozmiaru tablicy (np. dostęp do pierwszego elementu).
• D. O(n²): Złożoność kwadratowa; charakterystyczna dla algorytmów z zagnieżdżonymi pętlami przechodzącymi przez te same dane (np. proste sortowanie bąbelkowe).