Qual a complexidade da expressão: \sum_{i=0}^{n} i^{3} ? Dica: o somatório pode ser expresso pelo polinômio: n^{2}(n+1)^{2} / 4.

Passo 1

O enunciado pede para determinar a complexidade assintótica do somatório
\sum_{i=0}^{n} i^{3},
usando a expressão fechada dada pela dica. O conteúdo aqui é análise de complexidade de somatórios e identificação do termo dominante em um polinômio.

Passo 2

Pela dica, temos
\sum_{i=0}^{n} i^{3} \;=\;\frac{n^{2}(n+1)^{2}}{4}.
Para analisar a complexidade, expandimos esse polinômio:

Passo 3

Expandindo \frac{n^{2}(n+1)^{2}}{4} temos
\frac{n^{2}(n^{2}+2n+1)}{4} =\frac{n^{4}+2n^{3}+n^{2}}{4} =\frac{1}{4}n^{4}+\frac{1}{2}n^{3}+\frac{1}{4}n^{2}.
O termo de maior ordem é \frac{1}{4}n^{4}, que domina o comportamento para n grande.

Resposta

\Theta(n^{4})

Exercícios relacionados