Временная сложность функции со временем 1 + 8 + 27 + 64 + ... + sqrt(n)^3?

Question

Мне сказали, что

1 + 8 + 27 + 64 +... + (√n)³ = Θ (n²)

Почему это так?

Answer 1

Чтобы убедиться, что я понимаю, что вы говорите, вам любопытно, почему сумма

1³ + 2³ + 3³ +... + (√n)³ = Θ (n²)

Один из способов сделать это - найти формулу для суммы первых m кубов. Это равно

(м (м + 1) / 2)²

Итак, давайте подключим m = √n, что дает

1³ + 2³ + 3³ +... + (√n)³

= ((√n) ((√n) + 1) / 2)²

= ((n + √n) / 2)²

= (n² + 2n√n + n) / 4

Это окончательное выражение дает точное значение суммы первых √n совершенных кубов. Обратите внимание, что это выражение Θ (n²), потому что n² является доминирующим членом.

Надеюсь это поможет!