0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ (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. $\endgroup$
    – greybeard
    Commented Sep 13, 2020 at 17:50

1 Answer 1

1
$\begingroup$

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)$ .

$\endgroup$
2
  • $\begingroup$ I would say that $T(n) = n^3$, so $T(n) \in O(n^3)$. $\endgroup$ Commented Oct 13, 2020 at 3:11
  • $\begingroup$ @davidbuzatto. What you mean - we cannot write $n^3 \in O(n^3)$ or something else? $\endgroup$
    – zkutch
    Commented Oct 13, 2020 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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