Jaką złożoność obliczeniową mają problemy polegające na wykonaniu czynności na łańcuchu lub tabeli w dwóch zagnieżdżonych pętlach działających na wszystkich elementach?

Wybierz odpowiedź A O(n) B O(n2) C O(n!) D O(log n)

Pokaż odpowiedź i wyjaśnienie

Poprawna odpowiedź: B

O(n2)

Dlaczego

Dwie zagnieżdżone pętle po n elementach wykonują n · n operacji, więc złożoność to O(n²), czyli kwadratowa. Jedna pętla daje O(n).