CODEWITHSUNDEEP
cdata-structurestime-complexitybig-o
Jubran Jubran
Jubran Jubran

Reputation: 11

Three loops complexity

Can anyone tell me the complexity of the below code and explain the calculations?

int count=0;
for(int i=0; i<n;i++)
    for(int j=i; j<n;j++)
        for(int k=j;k>i;k--)
            count++;

Thanks

Upvotes: 0

Views: 156

Answers (1)

Adnan Isajbegovic
Adnan Isajbegovic

Reputation: 2307

This is just a "simple" math:

for first loop, its quite straightforward, it will do n iterations.

Second loop is not that much more complicated:

  • i=0: you will have n iterations.
  • i=1: n-1 iterations
  • i=2: n-2 iterations
  • ...
  • i=n-1: 1 iteration

Sum of it is n(n+1)/2.

For third loop, we are only interested when j>i:

  • i=n-1: you have 0 iteration.
  • i=n-2: 1 iteration, and that is when j=n-1
  • i=n-3: 2 iteration when j=n-1 and 1 iteration when j=n-2
  • i=n-4: 3 iteration when j=n-1, 2 iteration when j=n-2, 1 iteration when j=n-3
  • ...
  • i=0: n-1 iteration when j=n-1, n-2 iteration when j=2, ..., 1 iteration when j=1

Running time of this is:

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

Upvotes: 2

Related Questions