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 Sep 13 '20 at 17:50
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$ – davidbuzatto Oct 13 '20 at 3:11
  • $\begingroup$ @davidbuzatto. What you mean - we cannot write $n^3 \in O(n^3)$ or something else? $\endgroup$ – zkutch Oct 13 '20 at 8:16

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.