CODEWITHSUNDEEP
algorithmbig-ocomplexity-theory
Knowledge 32
Knowledge 32

Reputation: 9

Big O Notation for Nested Loop

I am trying to find time complexity for this Code. 

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

My Attempt: We can write this loop in the form:

for (int i = 1; i <= n; i++)
  for (int j = 1; j <= n; j++)
    for (int k = 1; k <= n; k++)

Now Big Oh of this loop is O(n^5). Am I correct or doing some mistake?

Upvotes: 1

Views: 6655

Answers (4)

Christos
Christos

Reputation: 53958

Now Big Oh of this loop is O(n^5). Am I correct or doing some mistake?

No, this is not correct. The time complexity is O(n^3).

In simple terms, you can think it off like this:

The maximum steps done in each for loop starting at 0 and reaching n-1 making steps of 1 are n. So if you have two loops, one nested in the other then for each step you make in the outer loop you make n steps in the nested loop. Given the steps you will make in the outer loop is n, it's pretty evident that at the end you will make n^2 steps.

Based on the above, you can easily draw that in the following case:

for(int i=0; i<=n-1; i++)
{
    for(int j=0; j<=n-1; j++)
    {
        for(int k=0; k<=n-1; k++)
        {

        }
    }
}

you will make n^3 steps. So the complexity is of the order of O(n^3).

Upvotes: 1

trincot
trincot

Reputation: 350137

The first variant of your code with a counter added:

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

This counts every combination of (i, j, k) with 0 <= i < j < k < n. This corresponds to the number of ways you can pick 3 elements from n elements, without taking the order of them into account. There is a formula for that number:

        n(n-1)(n-2) / 3! = n3/6 - n2/2 - n/2

The second variant:

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

... counts the number of ways you can pick 3 from n items, but where the order is important, and repetitions within the 3 selections are allowed. The number is quite easy to derive as i, j, k are independent and each can get n different values, so the total number is:

        n3

Now they represent the same time complexity:

        O(n3/6 - n2/2 - n/2) = O(n3)

This is because of the properties of big O:

if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard lower-order terms of the polynomial.

And:

Multiplication by a constant
Let k be a constant. Then:
O(kg) = O(g) if k is nonzero.

Upvotes: 6

Anita W
Anita W

Reputation: 101

Are those loops nested? If so, you're on the right track with rewriting the loop like that to make things easier to reason about. Although I would give each loop a different iterator name than i to avoid confusion:

for (int a = 1; a <= n; a++) {
    for (int b = 1; b <= n; b++) {
        for (int c = 1; c <= n; c++) {
            ...
        }
    }
}

In fact you could rename these variables to whatever you want to make things easier to reason about. How about:

for (int street = 1; street <= n; street++) {
    for (int house = 1; house <= n; house++) {
        for (int room = 1; room <= n; room++) {
            ...
        }
    }
}

Now, the problem becomes, if I have to visit n rooms in n houses in n cities, how many rooms do I have to visit?

Hopefully you can see that the answer is n * n * n , i.e. n^3.

The shortcut way of getting to the answer is just to see you have 3 nested for loops from 1 to n, so the answer is n^3.

Upvotes: 1

Jean-Fran&#231;ois Fabre
Jean-Fran&#231;ois Fabre

Reputation: 140158

if you have a doubt and you want to convince yourself just perform a little test:

#include <stdio.h>

int main()
{
int count1=0,count2=0;
int n=100;

for (int i = 0; i <= n - 1; i++)

for (int j = i + 1; j <= n - 1; j++)

for (int k = j + 1; k <= n - 1; k++)
  count1++;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

for (int k = 1; k <= n; k++)
  count2++;

printf("count1 %d count2 %d n %d\n",count1,count2,n);
return 0;
}

result:

count1 161700 count2 1000000 n 100

  • clearly, 2nd loop runs 100**3 times => O(n**3)

  • first loop runs less because of the bounds, but it's still linear (no divide operations on bounds) => O(n**3) as well even if it is faster.

Upvotes: 0

Related Questions