Take the 2-minute tour ×

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(j = i+1; j <= n; j++) {
           // 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 n = 9;
    int index_I = 0;
    int index_J = 0;
    int index_K = 0;
        for (int j = i+1; j <= n; j++) {
            for (int k = i; k <= j; k++) {
    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

share|improve this question

5 Answers 5

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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:

             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)

share|improve this answer

Your Answer


