Jaką złożoność obliczeniową ma algorytm wyszukiwania elementu w nieposortowanej tablicy jednowymiarowej?
Źle. Kwadratowa złożoność dotyczy np. zagnieżdżonych pętli, nie pojedynczego przejścia po tablicy.
Dobrze. W nieposortowanej tablicy w najgorszym razie sprawdza się wszystkie n elementów.
Źle. Złożoność silni rośnie skrajnie szybko - dotyczy np. permutacji, nie wyszukiwania.
Źle. Stała złożoność oznacza dostęp niezależny od rozmiaru, np. po indeksie - tu trzeba przeglądać elementy.
W nieposortowanej tablicy nie ma porządku, który pozwoliłby pominąć część elementów, więc element szuka się przeglądając kolejne pozycje (wyszukiwanie liniowe). W najgorszym przypadku trzeba sprawdzić wszystkie n elementów, dlatego złożoność wynosi O(n) - liniowa. Dlatego poprawna jest złożoność liniowa, O(n).
Pozostałe złożoności nie pasują do prostego przeglądania tablicy. Kwadratowa, O(n²), pojawia się przy zagnieżdżonych pętlach (np. niektóre sortowania) - tu wystarczy jedno przejście. Silnia, O(n!), rośnie ekstremalnie szybko i dotyczy problemów typu generowanie wszystkich permutacji, a nie wyszukiwania. Stała, O(1), oznacza operację niezależną od rozmiaru danych, np. odczyt po znanym indeksie - ale by znaleźć wartość w nieuporządkowanej tablicy, trzeba ją przeglądać. Najgorszy przypadek to sprawdzenie n elementów, czyli złożoność liniowa O(n).