CODEWITHSUNDEEP
algorithmbig-otime-complexitycomplexity-theoryasymptotic-complexity
User
User

Reputation: 1726

Why is this algorithm O(n^2) in complexity?

I know the big O complexity of this algorithm is O(n^2), but I cannot understand why.

int b=0;
for(int i=n; i>0; i--)
   for(int j=0; j<i; j++)
      b=b+5;

I know that the outer loop is O(n). I know that the inner loop will run n + (n-1) + (n-2) + ... + 1 times. That is as far as I can get. I am not sure where to go from there.

My question is, can somebody explain why that algorithm is O(n^2) ?

Upvotes: 0

Views: 120

Answers (3)

Sushil Dubey
Sushil Dubey

Reputation: 36

outer loop | inner loop
i=n       |   inner loop executes n times
i=n-1    |   inner loop executes n-1 times
i=n-2    |   inner loop executes n-2 times
.
.
.
i=1    | inner loop executes 1 time and exits

now summing up total no of times inner loop executes : n + (n-1) +(n-2)+.....+1= n*(n+1)/2 = O(n2)

Upvotes: 1

Incerteza
Incerteza

Reputation: 34884

Basically because there are n^2 more operations than in a single loop.

Upvotes: 0

Am_I_Helpful
Am_I_Helpful

Reputation: 19158

So, the total number of times the whole block of code would run 

= n + (n-1) + ...+ 1 
= n * (n+1) / 2 
= O(n^2).

The other statements would take O(1), so their's would have no effect(not much role) on complexity(their's being a constant).

Upvotes: 4

Related Questions