Dato un problema P si possono individuare diversi algoritmi risolutivi A1, A2, … Aq ciascuno con la sua complessità C1, C2, …, Cq.
Sia C* la complessità più bassa.
Se si dimostra che per il problema P non può esistere un algoritmo con complessità minore di C* allora si può affermare che il problema P ha complessità C*.
Problema della password
Le possibili sequenze di lunghezza n costruite con un alfabeto di 26 caratteri sono 26n
aa…a, aa…b, …, aa…z
…
zz…a, zz…b, …, zz…z
Sia c il tempo necessario per visualizzare una risposta allora il tempo necessario per visualizzare tutte le risposte è
T(n) = c·26n >> c·2n.
Il problema ha complessità (almeno) esponenziale O(2n).
Problema dell’anagramma
Consideriamo le permutazioni di n elementi qualsiasi
| Numero di caratteri | Permutazioni | Numero di permutazioni |
|---|---|---|
| 1 | a | 1 |
| 2 | ab, ba | 2 |
| 3 | abc, acb, bac, bca, cab, cba | 6 |
| 4 | abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda, bdac, bdca, cabd, cadb, cbad, cbda, cdab, cdba, dabc, dacb, dbac, dbca, dcab, dcba | 24 |
| 5 | … | 120 |
| … | … | … |
| n | … | n! |
Sia c il tempo necessario per visualizzare una risposta allora il tempo necessario per visualizzare tutte le risposte è
T(n) = c·n! >> c·2n
e quindi il problema ha complessità (almeno) esponenziale O(2n).
Problema del prodotto di matrici
Nel prodotto tra matrici di dimensioni nxn, C=AxB, è richiesto almeno il tempo
- T1(n)=c·n2, per scrivere i risultati in C
- T2(n)=2·c·n2, per leggere i dati in A e B
Non può esistere un algoritmo con complessità inferiore a quella necessaria per esaminare l’input oppure per generare l’output e quindi si parte comunque da una complessità quadratica.
L’algoritmo tradizionale che calcola il singolo elemento Cij tramite il prodotto scalare
Cij = Ai·Bj = Ai1·B1j+Ai2·B2j+…+Ain·Bnj
richiede n moltiplicazioni per ogni prodotto scalare e quindi richiede
T3(n) = c·n·n2 = c·n3
per calcolare tutti i prodotti.
Questo algoritmo potrebbe non essere il migliore (…) ma ci permette di stabilire un limite superiore per la complessità del problema.
In conclusione
T1(n) < T2(n) <= T(n) <= T3(n)
c·n2 <= T(n) <= c·n3
Il problema del prodotto matriciale ha una complessità compresa tra O(n2) e O(n3).
Vedi Algoritmo di Strassen: 
Problema dell’ordinamento
Per il problema dell’ordinamento esistono molti algoritmi con complessità diverse
| O(n2) | Ingenui | selection sort, bubble sort, shaker sort, insertion sort |
| O(n~1.2) | Intermedi | shell sort |
| O(n logn) | Evoluti | merge sort, quick sort, heap sort |
Si può dimostrare che non possono esistere algoritmi di ordinamento con complessità più bassa di O(n log n).
Il problema dell’ordinamento ha complessità O(n log n).