$$\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.
$$\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.
Hint: Factor out the (n-1) and then use that the average term in the sum has size n/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?