calculating Time complexity of a function

Question

Need help on how to calculate this time complexity

int func(int n) {
    int a = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= n - i; ++j) {
            for (int k = 0; k <= n - i; ++k) {
                for (int o = 1; o <= i; ++o) {
                    a++;
                }
            }
        }
    }
    return a;
}

Here is where I got it from, but I am not sure if this is correct and dont know how to continue.

Edit: I think I made some progress but I am not sure if this is correct.

Answer 1

We can get a closed formula for this.

The work done is reflected by the value of 𝑎 that is returned.

The inner three loops respectively iterate 𝑛 − 𝑖 + 1, 𝑛 − 𝑖 + 1 and 𝑖 times on their own, so in total, a++ executes 𝑖(𝑛 − 𝑖 + 1)² times, which is equivalent to 𝑖³ − 2(𝑛+1)𝑖² + (𝑛+1)²𝑖

We can analyse what the outer loop accumulates to for each of these three terms:

• The sum of the first term is a sum of a sequence of cubes, which is the square of the n^th triangle number: (𝑛(𝑛+1)/2)²

• The sum of the second term is the value −2(𝑛+1) multiplied by the sum of a sequence of squares, and that sum is a square pyramidal number, so we get -2(𝑛+1)𝑛(𝑛+1)(2𝑛+1)/6

• The sum of the third term is the value (𝑛+1)² multiplied by a triangular number, and so we get (𝑛+1)²𝑛(𝑛+1)/2

Add those three sums together and we get:

𝑛²(𝑛+1)²/4 − 2(𝑛+1)²𝑛(2𝑛+1)/6 + (𝑛+1)³𝑛/2

which simplifies to:

𝑛(𝑛+1)²(𝑛+2)/12 = O(𝑛⁴)

We can make a quick test by running the function with that formula (using JavaScript here):

function func(n) { // Original function
    let a = 0;
    for (let  i = 1; i <= n; ++i) {
        for (let j = 0; j <= n - i; ++j) {
            for (let k = 0; k <= n - i; ++k) {
                for (let o = 1; o <= i; ++o) {
                    a++;
                }
            }
        }
    }
    return a;
}

function closedForm(n) {
    return n*(n+1)*(n+1)*(n+2)/12;
}

// Run a few tests 
for (let n = 1; n < 20; n++) {
    console.log(func(n), closedForm(n));
}