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\\$




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.

  • $\begingroup$ 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$. $\endgroup$ – Peter Foreman Apr 16 '19 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$.

| cite | improve this answer | |
  • $\begingroup$ That makes perfect sense, thank you for that mihaild. I checked over the summation rules, and I didn't realise that it mentions the index. $\endgroup$ – WhatToDisplay Apr 16 '19 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.