Notacja Big O opisuje, jak rośnie czas wykonania algorytmu wraz ze wzrostem rozmiaru danych wejściowych n. Interesuje nas tempo wzrostu (górne ograniczenie), a nie dokładny czas, dlatego w Big O pomija się stałe mnożniki oraz składniki niższego rzędu.
W pytaniu mowa o czynnościach wykonywanych na łańcuchu lub tablicy w dwóch zagnieżdżonych pętlach, przy czym obie pętle przechodzą przez wszystkie elementy. To oznacza typowy schemat:
- pętla zewnętrzna: ~n iteracji,
- dla każdej iteracji zewnętrznej pętla wewnętrzna: ~n iteracji.
Liczba powtórzeń operacji w środku wynosi więc około n · n = n². W konsekwencji złożoność czasowa rośnie kwadratowo, czyli O(n²).
Dlaczego pozostałe odpowiedzi są niepoprawne?
- O(n) opisuje sytuację z jedną pętlą po wszystkich elementach lub gdy praca w środku jest stała i wykonywana raz na element. Przy dwóch pełnych pętlach zagnieżdżonych wzrost jest szybszy niż liniowy.
- O(log n) jest typowe dla algorytmów dzielących problem na połowy (np. wyszukiwanie binarne). Dwie pętle po wszystkich elementach nie powodują logarytmicznego spadku liczby kroków.
- O(n!) pojawia się np. przy generowaniu wszystkich permutacji (problemów kombinatorycznych). Zwykłe przejście dwoma pętlami po tablicy nie ma tak gwałtownego wzrostu.
Wskazówka egzaminacyjna: zawsze sprawdź, czy wewnętrzna pętla rzeczywiście wykonuje się n razy. Jeśli ma stały limit (np. do 10) albo jej zakres jest krótszy, wynik może być inny. W tym zadaniu warunek "na wszystkich elementach" jednoznacznie prowadzi do O(n²).
