CODEWITHSUNDEEP
algorithmperformancetime-complexity
Anatoly
Anatoly

Reputation: 1916

Complexity of triple-nested Loop

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?

Upvotes: 1

Views: 3581

Answers (2)

user5132172
user5132172

Reputation:

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:

enter image description here

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

We have

enter image description here

=

enter image description here ... Remember how to convert sums to polynomials

=

enter image description here

=

enter image description here

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

Upvotes: 12

IVlad
IVlad

Reputation: 43477

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.

Upvotes: 5

Related Questions