How to determine computational complexity for algorithms with nested loops?

Question

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

You have to write the total number of iterations using nested sums, then evaluate the sums. Note that while in many cases (as in your case) evaluating the sums will simply result in multiplying the total number of iterations per loop, this is not always the case; if the number of iterations in the inner loop grows you can't simply multiply them together. — user1726343
– user1726343, Commented Oct 29, 2015 at 18:44

EvilTeach · Accepted Answer · 2015-10-29 18:41:08Z

2

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)

answered Oct 29, 2015 at 18:41

EvilTeach

29k21 gold badges89 silver badges144 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Logan Over a year ago

Thanks for the answer @EvilTeach. Would you mind going into a little more detail how you determine the averages for the inner loops?

EvilTeach Over a year ago

Assume N is 5. The first row is 0, 1, 2, 3, 4 so O(N). The second row is {0, 1, 2, 3, 4}, {1, 2, 3, 4}, {2, 3, 4}, {3, 4}, {4} so 5 + 4 + 3 + 2 + 1 = 15 iterations, for the 5 iterations of the first loop. 15/5 is 3. which is about 5 / 2. Remember we are talking orders here. O(N/2) is the same as O(N). Using that as the general principle, the third loop will on average cover half the elements of loop 2 which is known to be about O(N/2) . This is about O(N/4). Multiple the 3 orders together yields about O(N^3). That was my thought pricess.

EvilTeach Over a year ago

It is kind of like doing a search for each key in an unordered array of keys. Sometimes you find it in the first couple of elements. Sometimes it's the last. On average, you need to look through about 1/2 the elements to find a given key.

EvilTeach Over a year ago

Another way of thinking about it is that each loop is processing about O(N) elements, hence the three loops yield O(N^3).

David Eisenstat Over a year ago

The third loop actually hits N/3 ± O(1) items on average, but that doesn't matter for big-O, since every loop instance has at most N iterations.

|

Collectives™ on Stack Overflow

How to determine computational complexity for algorithms with nested loops?

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related