Search code examples
algorithmbig-otime-complexitycomplexity-theoryasymptotic-complexity

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) ?

Solution

  • 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).