Help in finding complexity in Big O notation

Question

I'm trying to solve a problem from Project Euler and I found a solution where the iteration grows as follows: for level in tree: for current_node in current level: # create new list of next level nodes + current_node new_list = [node + current_node for node in next_level] That will repeat the number of nodes in the current level times the number or node in the next level. So I've come to this formula:

$$ 1\times2 + 2\times3 + 3\times4 + ... + (n-2)(n-1) + (n-1)n = \sum_{i=1}^{n-1} i(i+1) $$

I got the result then of $O(n^2)$, though I'm not sure if that's right. Would anyone give me some guidance in this problem?

Answer 1

Using

$\sum_{k=1}^p k = \frac{p(p+1)}{2}$ and $\sum_{k=1}^p k^2 = \frac{p(p+1)(2p+1)}{6}$

Since $\sum_{i=1}^{n-1} i(i+1) = \sum_{i=1}^{n-1} i+\sum_{i=1}^{n-1} i^2$, you will have that your complexity is $O(n^3)$ : bad news...

Answer 2

$$\sum_{i=1}^{n-1}i(i+1)=\frac13\sum_{i=1}^{n-1}[i(i+1)(i+2)-(i-1)i(i+1)]=\frac{n(n+1)(n-1)}3\sim O(n^3),$$

and this is actually one way to prove that $$\sum_{k=1}^p k^2=\frac{p(p+1)(2p+1)}6,$$ in the other answer. Not really relevant to the big-$O$, just a minor point.