CODEWITHSUNDEEP
javaalgorithmtime-complexitycomplexity-theory
Justin Trudeau
Justin Trudeau

Reputation: 31

Trying to calculate the time complexity of the following piece of code

Is the time complexity of the following piece of code O(n^5)? My reasoning is that the outer for loop is O(n), the middle for loop is O(n^2) since the value of i is based on the value of n, and the inner for loop is O(n^2) since the value of j is based on the value if i^2 which is based on the value of n^2.

int x = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i * i; j++) {
        for (int k = 0; k < j; k++) {
            x++;
        }
    }
}

Upvotes: 1

Views: 402

Answers (1)

xenteros
xenteros

Reputation: 15852

That is not that simple. To determine the complexity, one needs to calculate how many times the x will increase.

The most inner loop runs `j` times.
The middle loop runs `i*i` times.
The outer loop runs n times.

Let's reduce:

The middle loop's complexity is:

1+2+3+...+(i-1)+i+(i+1)+...+(i-1)*(i-1) = (i^2-2i+1)*i*i/2=(i^4-2i^3+i^2)/2

And the outer loop runs n times for each n from 0 to n-1. It sums up to:

n^5/10 - n^4/2 + 5n^3/6 - n^2/2 + n/15

and it's actually O(n^5).

The mathematical notation is:

enter image description here

Upvotes: 3

Related Questions