Combination : is a set
Permutation : is an ordered set

Permutations with repetition: n possibilities for the first choice, n for the second choice and so on:

\[ n^k \\ \]

*All* the permutations without repetition of a set N are given by

\[
n(n-1)(n-2)…(1) = n! \\
\]

whereas the permutations of, say, 3 items for a set of N elements are

\[ n(n-1)(n-2) \\ \]

which you can generalize to

\[\frac{n!} {(n – k)!} \\ \]

(For n = 5 it means \( { 5! \over 2!} = { 5 \times 4 \times 3 \times 2 \times 1 \over 2 \times 1} \) ).

If you want a combination of k itmes out of a set of N elements, you do permutations/redundancies; in terms of combination, a “redundency” is every single way you can arrange N elements… that is, the permutations of N. Therefore you sort of “undo” the permutation by dividing over k!, obtaining

\[
\frac{n!}{k!(n-k)!} = {n \choose k}
\]

In fact, we just saw that a combination of N elements has N! permutations. Therefore, given a permutation of N, it would suffice to divide it over N! to have a combination back.

However, this formula is called binomial factorial and reads n choose r. Keep in mind that when you find, say, \( n \choose 3 \) it is easier to solve it as \( {n(n-1)(n-1) \over 3! } \) rather than plug the values in the above formula and deal with a mess of calculations, where \( n(n-1)(n-2) \) is the worked out version of \( \frac{n!} {(n – k)!} \) for k being 3.

With this in mind, let’s see how to compute the order of growth of some little programs. Disclaimer: most of times is enough to pick the array accesses as a proxy for the running time, since it is often the most expensive operation.

2 Sum:

int count = 0;
for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
        if (a[i] + a[j] == 0)
            count++;

The number of different combinations of a[i] and a[j] here is \( n \choose 2 \) – that is, the number of times the j loop is executed; and each combination involves 2 array accesses. Therefore, the overall number of array accesses is given by

\[
{n \choose 2} = \frac {n(n-1)} {2!} \times 2 = \sim N^2 \\
\]

Obvious stuff to pay attention to:
-> \( n(n-1) \) is the result of \( {n! \over (n – k)!} \), as I just said above;
-> the order of growth for the j loop alone is \( {1 \over 2 }N^2 \), for the 2-sum is \( N^2 \).

If you manually “unroll” the loop, you’ll note indeed that the j-loop is executed n-1 times for the first i-loop (from 0+1 to 0+N), n-2 times for the second i-loop (from 1+2 to 1+N) for a total of \( (n-1) + (n-2) + (n-3) + … + 1 \), which is in fact \( {n (n-1) \over 2} \).

Another example:

3 Sum:

int count = 0;
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)
                count++;

Which is basically the same story: different combinations times array access for each inner loop yields

\[
{n \choose 3} = \frac {n(n-1)(n-2)} {3!} \times 3 = \sim {1 \over 6} N^3 \times 3 = \sim {1 \over 2} N^3 \\
\]

although the function describing only the k loop is \( \frac{n^3}{6} – \frac{n^2}{2} – \frac{n}{3} \).

Another example:

int sum = 0;
for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
        for (int k = 1; k < N; k = k*2)             
            if (a[i] + a[j] >= a[k])
                sum++

The k-loop is executed log(N) times, and each time it involves 3 accesses. The j-loop is the 2-sum \( {1 \over 2} N^2 \) , resulting in

\[
3 \times \log N + {1 \over 2} N^2 = {3 \over 2} N^2 \log N \\
\]

Another dependent nested loop:

for (j = 1; j < N; j++)
    for (k = 1; k < 3*j; k++)
        x = x + j;

The k-loop executes 3 times (1+2+3+…+ N), a well-known series.

\[
3 (1 + 2 + 3 + … + N) = 3 {n(n+1) \over 2} = {3 \over 2}N^2 + N \\
\]

Example:

int sum = 0;
for (int i = 0; i*i < N; i++)
    for (int j = 0; j*j < N*N*N; j++)
        sum++;

Note that the two loops here are completely independent from each other.

\[
N^\frac{1}{2} \times N^{ \frac{1}{2} \times 3} = N^2 \\
\]

Slightly tricky one:

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

The i-loop runs \(N^3 \) times, but the j-loop runs only if i < N.!
Therefore the oog is only \(N^3 + N\) and not \(N^4 \).