El bucle interno se repite j
veces, por lo que su complejidad es j*O(1).
Ese bucle está dentro de otro que se repite i
veces, mientras la j
varía. Por tanto cuando j=0
se realizan O(1)
operaciones, cuando j=1
serían 2*O(1)
operaciones, etc. hasta que j=i-1
en que se realizan i*O(1)
operaciones.
El bucle central (en el que varía j
) por tanto tendría una complejidad O(1)+2*O(1)+...+i*O(1)
. Llamemos a esa fórmula F(i)
.
Este bucle se realiza n
veces, mientras la i
va variando. Por tanto la primera vez su complejidad sería F(0), la segunda vez sería F(1), etc hasta F(n-1), siendo F(i) la fórmula antes dada O(1)+...+i*O(1)
.
Ahora veamos cuánto vale esa fórmula en cada paso:
i=0
, F(0) = O(1)
i=1
, F(1) = O(1) + 2*O(1)
i=2
, F(2) = O(1) + 2*O(1) + 3*O(1)
- ...
i=n-1
, F(n-1) = O(1) + 2*O(1) + 3*O(1) + ...+ n*O(1)
La complejidad final será la suma de todo lo anterior. Vemos que el término O(1)
aparece sumado n
veces, por tanto es un O(n)
. El término 2*O(1)
aparece sumado n-1
veces, por lo que sería 2*O(n-1)
, el término 3*O(1)
aparecería n-2
veces por lo que su suma sería 3*O(n-2)
, etc... hasta llegar al término n*O(1)
que aparece sumado una sola vez.
Si además tenemos en cuenta que los coeficientes 2*
, 3*
... n*
se pueden quitar puesto que no influyen en el orden de complejidad (es decir 2*O(n-1)
es lo mismo que O(n-1)
), se llega a que los tres bucles anidados dan una complejidad de O(n)+O(n-1)+...+O(2)+O(1)
, lo que explica tu fórmula.
Ahora bien, tengo mis dudas de que todo esto sea estrictamente correcto. La notación O(2) no significa nada en realidad al no aparecer ahí una variable y ya que la notación O-grande es una cota superior yo diría que no hace falta entrar en los detalles de que cada bucle anidado se va ejecutando cada vez menos veces que el que lo contiene, y diría directamente que el algoritmo tiene complejidad O(n3).