Algorytm o złożoności czasowej O(n²) przetwarza 1000 elementów w 2 s. Ile mniej więcej potrwa przetworzenie 3000 elementów?

Dlaczego tak

Przy złożoności kwadratowej czas rośnie proporcjonalnie do kwadratu rozmiaru danych. Trzykrotne zwiększenie n zwiększa czas 3² = 9 razy, więc 2 s · 9 = 18 s. Wynik 6 s odpowiadałby algorytmowi liniowemu O(n), 54 s — sześciennemu O(n³), a 9 s powstaje, gdy pomnoży się przez 9 nie czas, ale jego połowę.