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.
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 nth 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(𝑛4)
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));
}