# Compute the order of growth of a program

** Combination **: is a set

**: is an ordered set**

*Permutation*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

Therefore the oog is only \(N^3 + N\) and **not** \(N^4 \).