CODEWITHSUNDEEP
algorithmtime-complexity
roger_godement
roger_godement

Reputation: 13

What is the runing time of this algorithm?

Here is the snippet:

for(int i = 0; i < n; i++) {
    for(int j  = i + 1; j < n; j++) {
        //statements
    }
}

The outer loop runs (n) times
So the inner loop runs (Sum from k = 1 to n of (n - i)) * (n)

After algebraic manipulations, I get (n3 + n2) / 2. So, the running time is O(n3).

Could someone correct me if I am wrong ?

Thanks.

Upvotes: 1

Views: 80

Answers (4)

another_CS_guy
another_CS_guy

Reputation: 682

Usually when asked about time complexities, we tell the worst case time complexity. In your case, worst, best and average case are the same.

Outer loop runs n times, correspondingly inner loop runs (n - 1) + (n - ­2) + ..... + 1. times for different value of i in outer loop, which is AP and sum is n(n-1)/2.

You might be multiplying running of inner loop with outside loop complexity, thatswhy you are getting time complexity as O(n^3).

Actual time complexity is Θ(n^2) for your algorithm

Upvotes: 0

Vishal_898
Vishal_898

Reputation: 300

Suppose your n is equal to 5

Then the inner loop will run 5 times

first time for 4 times;

second time for 3 times;

third time for 2 times;

fourth time for 1 time;

fifth time for 0 times;

So total time will be 4+3+2+1+0. This is equal to sum first (n) natural numbers and it is given by ((n)*(n+1))/2. So by this, we can say that complexity is of order O(n^2).

Upvotes: 2

Carlos
Carlos

Reputation: 6021

Your loop ends up looking like this for a small example:

   1 2 3 4
     2 3 4
       3 4
         4

Clearly it's a triangle of some sort, the Big-O of which is n^2 since we don't care about the constant.

Even if you just started the inner loop at the same index as the outer loop, you'd have a square of 1 2 3 4 etc instead, but that would also be n^2

Upvotes: 1

Giorgi Tsiklauri
Giorgi Tsiklauri

Reputation: 11136

Your outer loop runs n times.

The number of running time of your inner loop, decreases per each iteration of outer loop. So the total number of times the statements (body of your inner loop) execute, is:

(n - 1) + (n - ­2) + ..... 2 + 1.

which is n * (n - ­1) / 2, which, in turn, is (n2 - n) / 2.

Hence we can say that the running time of your algorithm is O(n2).

Upvotes: 0

Related Questions