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.

  • 0
    This question would be much improved if it were formatted in LaTeX, i.e. $\sum_{i=0}^{n-1} (i+1)(n-1)$. I'd change it myself but now that we're out of private beta I can't edit anymore.2010-12-08
  • 0
    http://www.codecogs.com/latex/eqneditor.php - you can use this to type up your equations enclose whatever this gives you in dollar signs and it should display properly2010-12-08
  • 5
    They're not mutually exclusive, y'know!2010-12-08
  • 0
    wat does that mean?2010-12-08
  • 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
    errr... im really bad at maths:S would that be O(n^2) i presume?2010-12-08
  • 0
    Do you know how much is 1 + ... + n?2010-12-08
  • 0
    yes its n*n+1 /22010-12-08
  • 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