# Algorithm Complexity - Summation - Correctly interpreted how to do it.

I wanted to double check my understanding and working out for a 3 nested for loop algorithm, and working out it's complexity. I've got the right answer, but how I've arrived at it I feel isn't exactly correct.

$$\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\sum_{k=0}^{n-1} 1\\$$

$$\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} n\\$$

$$\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} n*1\\$$

$$n\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} 1\\$$

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

$$n^2\sum_{i=0}^{n-1}1\\$$

$$n^3\\$$

Essentially, I move the $$n$$ outside the summations, based on the sum manipulation rules. However, I feel this is incorrect given it should only be constants that are moved outside the summation.

If that's the case, I'm not too sure how to arrive at the $$n^3$$ answer, if we can't "move" the $$n$$ outside. Any help would be much appreciated.

• It is valid to move the $n$ outside of the summations because all of the summations are finite and have indices that are not dependent on $n$. – Peter Foreman Apr 16 at 22:44

It is correct. You can move any multiplier that doesn't depend on index of summation, and $$n$$ doesn't depend on $$i$$, $$j$$, $$k$$.