La complejidad del algoritmo que presentas es O(n^3).
Vamos a asumir una subrutina f() que se ejecuta en tiempo constante.
Queremos saber cuántas veces llamamos a esta subrutina en función de n.
Ahora bien, si solo tuvieras el while más externo, tendríamos algo así
int i = 0;
while (i < n - 2) {
f() // Recuerda que una llamada a esta función es constante
i++;
}
Tomemos algunos valores de n para ver cuantas veces se llama la subrutina f.
Para n = 2
Se llama 0 veces por lo que la condición del ciclo no se cumple ni la primera vez.
Para n = 4
La subrutina f será llamada 2 veces. (i = 0, i = 1)
Para n = 100
La subrutina f será llamada 98 veces.
En general
La subrutina f se llamará O(n-2) veces.
Ahora bien, cuando hablamos de complejidad algorítmica, nos preocupamos por la tasa a la que crece un algoritmo con respecto a la entrada, por lo que las constantes se omiten.
Entonces tenemos que esta parte es O(n).
Ahora, seguimos con el ciclo for.
int i = 0;
while (i < n - 2) {
for (int j = i + 1; j < n - 1; j++) {
f();
}
i++;
}
Sabemos que el while se ejecuta O(n) veces. La pregunta es entonces ¿cuantas veces se ejecuta el for por cada una de esas n veces?.
Para n = 5
Para i = 0;
f será llamada cuando j = 1, 2, 3 (3 veces)
Para i = 1;
f será llamada cuando j = 2, 3 (2 veces)
Para i = 2;
f será llamada cuando j = 3 (1 vez)
Por lo que tenemos que el número total de veces que se llama a f es 3+2+1 cuando n = 5.
Para el caso general esto se reduce a una sumatoria.
1 + 2 + ... + (n-3) + (n-2) = (n-2) * (n-1) / 2
(n-2) * (n-1) / 2 = O(n^2)
Tenemos que la complejidad es de O(n^2)
Finalmente, al agregar el ciclo más anidado.
int i = 0;
int k = 0;
while (i < n - 2) {
for (int j = i + 1; j < n - 1; j++) {
k = j + 1;
while (k < n) {
f();
k++;
}
}
i++;
}
Ya sabemos que el while más afuera y el for son O(n^2).
Analicemos el mismo caso que teníamos antes cuando n = 5.
Para i = 0, j = 1; f será llamado cuando k = 2, 3, 4 (3 veces)
Para i = 0, j = 2; f será llamado cuando k = 3, 4 (2 veces)
Para i = 0, j = 3; f será llamado cuando k = 4 (1 vez)
Para i = 1, j = 2; f será llamado cuando k = 3, 4 (2 veces)
Para i = 1, j = 3; f será llamado cuando k = 4 (1 vez)
Para i = 2, j = 3; f será llamado cuando k = 4 (1 vez)
En total se llamó 10 veces.
En general la subrutina f se llama la siguiente cantidad de veces.
Nótese que aunque 5^3 = 125, solo se ejecuta 10 veces para ese caso f.
Esto es porque este tipo de análisis se preocupa para cuando la entrada se vuelve más grande. Por ejemplo, este algoritmo resulta impráctico si hubiesen 10000 elementos, por lo que la subrutina f se ejecutaría cerca de 166x10^9 veces.
Como curiosidad la sumatoria anterior es igual a
O(n + n(n + 1)(n - 4) / 6)
O(n^3/6 - n^2/2 + n/3)