Complexity of triple-nested Loop

Question

I have the following algorithm to find all triples

for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
         for (int k = j+1; k < N; k++)
             if (a[i] + a[j] + a[k] == 0)
                { cnt++; }

I now that I have triple loop and I check all triples. How to show that the number of different triples that can be chosen from N items is precisely N*(N-1)*(N-2)/6 ?

If we have two loops

for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
             ...

when i = 0 we go to the second loop N-1 times

i = 1 => N-2 times

...

i = N-1 => 1 time

i = N => 0 time

So 0 + 1 + 2 + 3 + ... + N-2 + N-1 = ((0 + N-1)/2)*N = N*N - N/2

But how to do the same proof with triples?

Check out this article: en.wikipedia.org/wiki/Combination#Number_of_k-combinations — default locale
– default locale, Commented Aug 11, 2015 at 9:18

score 12 · Accepted Answer · 2015-08-12 10:09:35Z

Ok, I'll do this step by step. It's more of a maths problem than anything.

Use a sample array for visualisation:

[1, 5, 7, 11, 6, 3, 2, 8, 5]

The first time the 3rd nested loop begins at 7, correct?

And the 2nd at 5, and the 1st loop at 1.

The 3rd nested loop is the important one.

It will loop through n-2 times. Then the 2nd loop increments.

At this point the 3rd loop loops through n-3 times.

We keep adding these till we get.

[(n-2) + (n-3) + ... + 2 + 1 + 0]

Then the 1st loop increments, so we begin at n-3 this time.

So we get:

[(n-3) + ... + 2 + 1 + 0]

Adding them all together we get:

[(n-2) + (n-3) + ... + 2 + 1 + 0] +
[(n-3) + ... + 2 + 1 + 0]         +
[(n-4) + ... + 2 + 1 + 0]         +
.
.                                     <- (n-2 times)
.
[2 + 1 + 0]                       +
[1 + 0]                           +
[0]

We can rewrite this as:

(n-2)(1) + (n-3)(2) + (n-4)(3) + ... + (3)(n-4) + (2)(n-3) + (1)(n-2)

Which in maths notation we can write like this:

Make sure you look up the additive properties of Summations. (Back to college maths!)

We have

=

... Remember how to convert sums to polynomials

=

Which has a complexity of O(n^3).

IVlad · Accepted Answer · 2015-08-11 09:23:35Z

One way is to realize that the number of such triples is equal to C(n, 3):

              n!
C(n, 3) =  --------
           3!(n-3)!

        = (n-2)(n-1)n/6

Another is to count what your loops do:

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

You've already showed that two loops from 0 to n-1 execute n(n-1)/2 operations.

For i = 0, the inner loops execute (n-1)(n-2)/2 operations.

For i = 1, the inner loops execute (n-2)(n-3)/2 operations.

...

For i = N - 1, the inner loops execute 0 operations.

We have:

(n-1)(n-2)/2 + (n-2)(n-3)/2 + ... =

= sum(i = 1 to n) {(n - i)(n - i - 1)/2}
= 1/2 sum(i = 1 to n) {n^2 - ni - n - ni + i^2 + i}
= 1/2 sum(i = 1 to n) {n^2} - sum{ni} - 1/2 sum{n} + 1/2 sum{i^2} + 1/2 sum{i}
= 1/2 n^3 - n^2(n+1)/2 - 1/2 n^2 + n(n+1)(2n+1)/12 + n(n+1)/4

Which reduces to the right formula, but it gets too ugly to continue here. You can check that it does on Wolfram.

Collectives™ on Stack Overflow

Complexity of triple-nested Loop

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related