1
$\begingroup$

$\sum_{i=0}^{n-1} (i+1)(n-1)$

Is that $O(n^2)$ or $O(n^3)$? Can you explain me how you found it? Thanks.

  • 3
    An expression being $O(n^2)$ as $n \to \infty$ means, loosely-speaking, that the expression's growth rate is no larger than quadratic. Since no larger than quadratic means no larger than cubic, any expression that is $O(n^2)$ is also $O(n^3)$. That's what Qiaochu Yuan's comment means.2010-12-08

2 Answers 2

7

Hint: Factor out the (n-1) and then use that the average term in the sum has size n/2.

  • 0
    aw ok so , its O(n^3$)$ since the inner bracket is n^2 and you multiply by N right?2010-12-08
2

Ok .. so from what Noah Snyder says, that will be: $(n-1)\sum_{i=0}^{n-1} (i+1)$.

The inner summation is $O(n^2)$, and the outer factor is $O(n)$, so overall this has $O(n^3)$ complexity, right?

  • 0
    Yup that's the idea.2010-12-08