Jest to liczba głównych operacji jakie wykonuje nasz algorytm. Pozwala ona nam określić jego wydajność (opłacalność). Możemy ją podzielić na pamięciową – ilość pamięci jaką program wykorzystuje i czasową – w jakim czasie program się wykona.

Złożoność zapisujemy w następujący sposób: O(najbardziej pesymistyczna ilość obliczeń wykonywanych przez algorytm)

Najbardziej podstawowe rodzaje złożoności (od najwydajniejszej do najmniej wydajnej):

• Stała -> O(1)

program wykonuje się w jednym kroku bądź liczba kroków nie zależy od podawanych przez użytkownika danych

• Logarytmiczna -> O(log n)

Szybsza i wydajniejsza od liniowej.

• Liniowa -> O(n)

Najczęściej występuje, gdy program składa się z jednej pętli.

• Kwadratowa -> O()

Najczęściej, kiedy spotykamy się z pętlą w pętli.

• Wielomianowa -> O()
• Silnia -> O(n!)

tego typu algorytmy są już bardzo niewydajne

• Wykładnicza -> O()

Jeżeli w naszym zadaniu okazuje się że największą możliwą liczbą danych na jakich będziemy wykonywać operacje jest 10, to:

dla złożoności liniowej wykonamy O(10), czyli 10 operacji, a dla kwadratowej już O(10*10), czyli 100 operacji.