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