Como calcular o Big-O a complexidade do algoritmo a seguir?

Question

Estou tentando calcular o Big-o do seguinte algoritmo que vem a ser O(n^5) para mim.Eu não sei o que a resposta correta é, mas a maioria dos meus colegas estão recebendo 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;
        }
     }
}

O que eu fiz foi começar a partir do mais íntimo do loop.Então eu calculei que o mais íntimo do loop será executado n/2 vezes, em seguida, fui para a segunda nested loop for que será executado i^2 tempos e do externo loop será executado i vezes i varia de 1 para n.Isso significa que o segundo aninhados para loop será executado um total de Sigma(i^2) from i=1 to i=n assim, um total de n*(n+1)*(2n+1)/6 vezes.Assim, o montante total que o código seria executado veio a ser na ordem de n^5 assim, entendo que a ordem deve ser O(n^5).Há algo de errado com esta abordagem e a resposta que eu calculado?

Eu só comecei com DSA e esta foi a minha primeira atribuição portanto, pedimos desculpas por quaisquer erros básicos que eu poderia ter feito.

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;
        }
     }
}

Triplo loop aninhado é equivalente à soma $$\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)$$

---

Em termos de real código eficiência, uma vez que x=y+z é invariante no loop, qualquer boa otimização do compilador irá extrair a instrução do loop (no compilador falar, talha, a instrução para o ciclo preheader) e, portanto, tornando o código compilado em executar $S(1)$.