nested for loops with changing variables time complexity

Question

i've searched around for some help on time complexity, and wasn't able to find much when the variables inside the for loops are all changing based on the prior for loops. I wrote the function up in code, and ran it to try to further my understanding, however I'm just not able to grasp it and put it into a formula. Maybe if someone could show me some tips on how to visualize the formula, that would be awesome! Without further ado here is the function I wrote up:

    public static void function2(){
Scanner scanner = new Scanner(System.in);
System.out.println("enter a value for n: ");
int n = scanner.nextInt();
int counter = 0;
for (int i = 1; i <= (n-2); i++){
    System.out.println("Entered outer loop");
    for (int j = i+1; j<= (n-1); j++){
        System.out.println("Entered middle loop");
        for (int k = j+1; k<= n; k++){
            System.out.println("Entered inner loop");
            System.out.println("Hello World");
            counter++;
        }
    }
}
 System.out.println("Hello world printed: " + counter + " times");
}

So i've ran the function based on different input sizes, and have gathered these results: if n = (number), Hello world is printed xtimes, n=5, 10x, n=6, 20x, n=7, 35x, n=8, 56x, n=9, 84x, n=10, 120x

I've graphed it, and understand it is a function that grows as an exponential rate, however I'm not sure what the precise formula would be for this. I also see that when n=5, hello world gets output in a patttern of, n-2, n-3, n-4 times, then goes back to the middle loop, and then back to inner, running n-3, n-4 times, back to the middle, and then back to inner to run n-4 times.

If someone could help me visualize this better, or point me in the right direction, that would be awesome! I feel as though I'm very close to the answer. Thanks for your time!

BonzaiThePenguin · Accepted Answer · 2014-05-11 22:00:22Z

1

This is O(n^3), since the constants and lower-order terms are discarded for time complexities.

If we didn't discard those things, it'd be (n - 2) * (n - 1)/2 * n/3. You can derive this equation yourself by doing the following:

int n = 1000;
int loop1 = 0, loop2 = 0, loop3 = 0;
for (int i = 1; i <= (n-2); i++){
    loop1++;
    for (int j = i+1; j<= (n-1); j++){
        loop2++;
        for (int k = j+1; k<= n; k++){
            loop3++;
        }
    }
}
printf("%d %d %d\n", loop1, loop2, loop3);

For n = 1000, this prints "998 498501 166167000". To get from 998 to 498501 we multiply by 499.5, which is (n - 1)/2. To get from 498501 to 166167000, we multiply by 333.3333, which is n/3. And 998 is obviously (n - 2). Put it together and you get (n - 2) * (n - 1)/2 * n/3.

If you simplify it, you get this:

(n - 2) * (n - 1)/2 * n/3
(n - 2) * (n/2 - 1/2) * n/3
(n - 2) * (n/2 * n/3 - 1/2 * n/3)
(n - 2) * ((n^2)/6 - n/6)
(n^2)/6 * (n - 2) - n/6 * (n - 2)
n * (n^2)/6 - 2 * (n^2)/6 + n * -n/6 - 2 * -n/6
(n^3)/6 - (n^2)/3 - (n^2)/6 + n/3

(n^3)/6 - (n^2)/2 + n/3

But since we do remove constants and lower-order terms, that simplifies to O(n^3).

edited May 11, 2014 at 22:00

answered May 11, 2014 at 21:40

BonzaiThePenguin

1,43313 silver badges19 bronze badges

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

5 Comments

apollo701 Over a year ago

Thank you! Makes perfect sense. However--lets say I was asked this question on an exam, and didn't have access to a computer where I could type up this code to count how many iterations happen per loop. How would I go about deriving (n-2) * (n-1)/2 * n/3 ? the (n-2) part is very clear, the n-1/2 somewhat makes sense, and the n/3, i'm just not sure about.

BonzaiThePenguin Over a year ago

You should open up a new question for that which links back to this one for reference, since comments don't allow multiple lines or long explanations.

BonzaiThePenguin Over a year ago

However, to correctly determine that it's O(n^3) all you need to do is note that it's a triple-nested loop over n, and that since the constants and lower-order terms don't matter there's no point in figuring out what they are.

GameAlchemist Over a year ago

+1, but i didn't get why you do the compute in your post : you said it all in your first phrase, so no use in computing terms you'll discard right after. And by 'derive' you must mean deduce or compute, because anyway the nearest valid math word is derivative and means something else.

BonzaiThePenguin Over a year ago

Deriving means obtaining information by doing something, and is used all the time in mathematics and other logical fields.

Collectives™ on Stack Overflow

nested for loops with changing variables time complexity

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related