CODEWITHSUNDEEP
algorithmbig-ocomplexity-theory
Logan
Logan

Reputation: 1804

How to determine computational complexity for algorithms with nested loops?

After looking at this question, this article, and several other questions, I have still not been able to find a general way to determine the computational complexity of algorithms with looping variables dependent on the parent loop's variable. For example,

   for (int i = 0; i < n; i++) {
       for (int j = i; j < n; j++) {
           for (int k = i; k < j; k++) {
               //one statement
           }
       }
   }

I know that the first loop has a complexity of n, but the inner loops are confusing me. The second loop seems to be executed n-i times and the third loop seems to be executed j-i times. However, I'm not sure how to turn this into a regular Big-O statement. I don't think I can say O(n(n-i)(j-i)), so how can I get rid of the i and j variables here?

I know this is something on the order of n^3, but how can I show this? Do I need to use series?

Thanks for your help!

(If you were wondering, this is from a brute force implementation of the maximum sum contiguous subsequence problem.)

Upvotes: 3

Views: 463

Answers (1)

EvilTeach
EvilTeach

Reputation: 28882

  • First loop hits N items on average.
  • Second loop hits N / 2 items on avarage
  • Third loop hits N / 4 items on average

O(N * N / 2 * N / 4) is about O((N^3)/8) is about O(N^3)

Upvotes: 2

Related Questions