¿Cómo calcular la complejidad Big-O del siguiente algoritmo?

Question

He estado intentando calcular el Big-O del siguiente algoritmo y el resultado es O(n^5).No sé cuál es la respuesta correcta, pero la mayoría de mis colegas obtienen O(n^3).

for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++) 
        {
        x = y + z;
        }
     }
}

Lo que hice fue empezar desde el bucle más interno.Entonces calculé que se ejecutará el bucle más interno. n/2 veces, luego fui al segundo bucle for anidado que se ejecutará i^2 veces y desde el bucle más externo se ejecutará i veces como i varía de 1 a n.Esto significaría que el segundo bucle for anidado ejecutará un total de Sigma(i^2) from i=1 to i=n entonces un total de n*(n+1)*(2n+1)/6 veces.Entonces, la cantidad total que ejecutaría el código resultó ser del orden de n^5 así que concluí que el orden debe ser O(n^5).¿Hay algún problema con este enfoque y la respuesta que calculé?

Acabo de empezar con DSA y esta fue mi primera tarea, así que me disculpo por los errores básicos que pueda haber cometido.

Answer 1

for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++) 
        {
        x = y + z;
        }
     }
}

El bucle triple anidado es equivalente a la suma$$\sum_{i=1}^{n}\sum_{j=1}^{i^2} \sum_{k=1}^{n/2} 1$$ $$=\frac{n}{2}(\sum_{i=1}^{n}\sum_{j=1}^{i^2}1)$$ $$=\frac{n}{2}(\sum_{i=1}^{n}i^2)$$ $$=\frac{n}{2} \cdot (\frac{1}{6}n(n+1)(2n+1))$$ $$=O(n^4)$$

---

En términos de actual eficiencia del código, ya que x=y+z es invariante en el bucle, cualquier buen compilador de optimización extraerá la declaración fuera del bucle (en el lenguaje del compilador, elevará la declaración al preencabezado del bucle), lo que hará que el código compilado se ejecute en $O(1)$.