# How to calculate the runtime of a following code?

Could someone explain how to calculate the Big O notation for a runtime of a snippet of a code?

for (int i=0; i<list.length; i++) {
for (int j=0; j<list.length; j++) {
for (int k=0; k<list.length; k++) {
if (k%2==0) {
list[i] += list[j];
} else {
list[i] += list[k];
}
}
}
}


From my understanding, I'm thinking it's something like O(n^3) because the statement is executive n times for every i?

• (This would depend on the static evaluation (some of which is known under the name of code improvement (Marketese: Code Optimization)) performed - how would you "do it using pen&paper"?) There have been discussions What to do when the answer is already part of the question. – greybeard Sep 13 '20 at 17:50

If I understand correctly, that you denote $$n$$=list.length and are calculating amount of "list[i] +=" operation. Then of course, as it is triple loop, then for $$n$$ times fixed "i" from first loop you take $$n$$ times "j" from second loop and $$n$$ times "k" from most inner, third, loop. So operation "list[i] +=" will be fulfilled exactly $$n^3$$ times. Now knowing, that $$n^3 \in O(n^3)$$ you can state that complexity for whole snippet is $$O(n^3)$$ .
• I would say that $T(n) = n^3$, so $T(n) \in O(n^3)$. – davidbuzatto Oct 13 '20 at 3:11
• @davidbuzatto. What you mean - we cannot write $n^3 \in O(n^3)$ or something else? – zkutch Oct 13 '20 at 8:16