3

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

Community
  • 1
  • 1
Logan
  • 1,575
  • 1
  • 17
  • 26
  • 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. – Asad Saeeduddin Oct 29 '15 at 18:44
  • 1
    `for (int j = i; i < n; j++) {` that's not foing to stop – amit Oct 29 '15 at 18:53
  • @amit Shoot! Thank you, I corrected that. – Logan Oct 29 '15 at 19:27

1 Answers1

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)

EvilTeach
  • 28,120
  • 21
  • 85
  • 141
  • Thanks for the answer @EvilTeach. Would you mind going into a little more detail how you determine the averages for the inner loops? – Logan Oct 29 '15 at 19:33
  • 1
    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 Oct 29 '15 at 19:57
  • 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 Oct 29 '15 at 20:04
  • Another way of thinking about it is that each loop is processing about O(N) elements, hence the three loops yield O(N^3). – EvilTeach Oct 29 '15 at 20:06
  • 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. – David Eisenstat Oct 29 '15 at 21:27
  • ya. We aren't going for a rigorous proof here, more of a proof of concept demonstration. The other one I keep in my head is the binary search type, which ends up O(logbase2 (N)) Those will get you through most Order estimates. I think for me the big leap was the fact that O(2N) = O(N). Order notation is not really for exact compares, but is for Order of Magnitude compares. For sufficiently large N, there isn't a lot of difference between O(2N) and O(N), so you can reduce it in one step. – EvilTeach Oct 29 '15 at 22:42
  • @EvilTeach Thank you for the good answer! I'm still slightly confused on figuring out the complexity of the third loop, but I think I get the point. – Logan Oct 30 '15 at 04:36