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!

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