CODEWITHSUNDEEP
big-o
HMdeveloper
HMdeveloper

Reputation: 2884

running time of algorithm does not match the reality

I have the following algorithm:

enter image description here

I analyzed this algoritm as follow:

Since the outer for loop goes from i to n it iterates at most n times, and the loop on j iterates again from i to n which we can say at most n times, if we do the same with the whole algorithm we have 4 nested for loop so the running time would be O(n^4).

But when I run this code for different input size I get the following result:

enter image description here

As you can see the result is much closer to n^3? can anyone explain why does this happen or what is wrong with my analysis that I get a loose bound?

Upvotes: 1

Views: 211

Answers (3)

gnasher729
gnasher729

Reputation: 52602

You are having a rather complex algorithm. The number of operations is clearly less than n^4, but it isn't at all obvious how much less than n^4, and whether it is O (n^3) or not.

Checking the values n = 1 to 9 and making a guess based on the results is rather pointless.

To get a slightly better idea, assume that the number of steps is either c * n^3 or d * n^4, and make a table of the values c and d for 1 <= n <= 1,000. That might give you a better idea. It's not a foolproof method; there are algorithms changing their behaviour dramatically much later than at n = 1,000.

Best method is of course a proof. Just remember that O (n^4) doesn't mean "approximately n^4 operations", it means "at most c * n^4 operations, for some c". Sometimes c is small.

Upvotes: 1

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Formally, you may proceed like the following, using Sigma Notation, to obtain the order of growth complexity of your algorithm:

enter image description here

Moreover, the equation obtained tells the exact number of iterations executed inside the innermost loop:

int sum = 0;
for( i=0 ; i<n ; i++ )
    for( j=i ; j<n ; j++ )
        for( k=0 ; k<j ; k++ )
            for( h=0 ; h<i ; h++ )
                sum ++; 
printf("\nsum = %d", sum);

When T(10) = 1155, sum = 1155 also.

Upvotes: 2

mbroshi
mbroshi

Reputation: 979

I'm sure there's a conceptual way to see why, but you can prove by induction the above has (n + 2) * (n + 1) * n * (n - 1) / 24 loops. Proof left to the reader.

In other words, it is indeed O(n^4).

Edit: You're count increases too frequently. Simply try this code to count number of loops:

    for (int n = 0; n < 30; n++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                for(int k = 0; k < j; k++) {
                    for (int h = k; h < i; h++) {
                        sum++;
                    }
                }
            }
        }
        System.out.println(n + ": " + sum + " = " + (n + 2) * (n + 1) * n * (n - 1) / 24);
    }

Upvotes: 1

Related Questions