CODEWITHSUNDEEP
algorithmcomplexity-theorybig-otime-complexity
user2725108
user2725108

Reputation: 151

What is the complexity of this nested triple for loop?

I have searched a bit on StackOverflow and have understood the complexity up to the point of the j-loop, which is O(n2). However with the nested addition of the k-loop, I am confused as why the complexity becomes O(n3). Can someone help me understand this?

From my understanding, the i-loop have n iterations and the j-loop have 1+2+3+...+n iterations n*(n+1)/2 which is O(n2).

for(i = 1; i < n; i++) {   
    for(j = i+1; j <= n; j++) {
        for(k = i; k <= j; k++) {
           // Do something here...
        }
    }
}

EDIT: Thanks for all your help guys :) Balthazar, I have written a piece of code to which will increment counters depending on which loop they are in, kinda a crude way of step-by-step:

#include <iostream>

int main(int argc, const char * argv[])
{
    int n = 9;
    int index_I = 0;
    int index_J = 0;
    int index_K = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            for (int k = i; k <= j; k++) {
                index_K++;
            }
            index_J++;
        }
        index_I++;
    }
    std::cout << index_I << std::endl;
    std::cout << index_J << std::endl;
    std::cout << index_K << std::endl;
    return 0;
}

I ran this code from n=2 to n=9 with increments of 1 and have got the following sequence:

From the counters, it can therefore be seen that: i = n-1 giving the complexity of O(n) and j = ((n-1)*n)/2 giving the complexity O(n2). A pattern for K was hard to spot but it is known that K depends on J, therefore:

k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6 giving a complexity of O(n3)

I hope this will help people in the future.

EDIT2: thanks Dukeling for the formatting :) Also found a mistake in the last line, corrected now

Upvotes: 15

Views: 47599

Answers (5)

napendra
napendra

Reputation: 378

First we'll consider loops where the number of iterations of the inner loop is independent of the value of the outer loop's index. For example:

for (i = 0; i < N; i++) {
      for (j = 0; j < M; j++) {
             sequence of statements
      }
  }

The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times.
Thus, the total complexity for the two loops is O(N2).
Similarly the complexity for the three loops is O(N3)

Upvotes: 1

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

If you're accustomed to Sigma Notation, here is a formal way to deduce the time complexity of your algorithm (the plain nested loops, precisely):

enter image description here

NB: the formula simplifications might contain errors. If you detect anything, please let me know.

Upvotes: 21

jambono
jambono

Reputation: 408

the k-loop has O(j-i) complexity

the j-loop has O((n-i)*(n-i)) complexity

the i-loop has O(n*n*n)=O(n^3) complexity

anyway, you know that it is not O(n^2) because the first two loops are O(n^2) and it is not more than O(n^3) because there are only 3 loops

Upvotes: 7

dividebyzero
dividebyzero

Reputation: 56

This is quite tricky to explain without diagrams, but each nested loop will iterate "n" number of times before returning the iteration to the parent.

So as jambono points out, each nested loop requires comparison/evaluation for each iteration of "n". So "n" is compared to the local variables in each loop (n*n*n) making O(n^3).

Step the code in a debugger for a visual indication of how this complexity is processed by the machine.

Upvotes: 1

Vladimir Georgiev
Vladimir Georgiev

Reputation: 1949

Take a look at this example for evaluating worst case complexity.

In essence, if you evaluate it line by line, you will get to something like O(n^3 / C), where C is some constant, normally skipped in such evaluations, leading to O(n^3).

Upvotes: 2

Related Questions