# Compute the order of growth of a program

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$$.