# Counting steps

Since we’re beginning this course in discrete mathematics with a focus on counting and since we’re mostly computer science majors, let’s take a look at how counting comes up in the analysis of algorithms. In the process, we might bump into a new friend.

## Computing powers

Suppose we wish to compute $$a^n$$ for a given real number $$a$$ and non-negative integer $$n$$. I guess the obvious way to accomplish this is like so:

function simple_power(a, n) {
let result = a;
for (let i = 1; i < n; i++) {
result = a * result;
}
return result;
}

An important question in the analysis of algorithms is:

How many arithmetic operations does this process take?

In this particular example, It’s pretty easy to see that the answer is $$n-1$$, since there’s one multiplication required for each step through the the loop from $$1$$ up to one less than $$n$$. In more complicated examples, we might wish to add code to count the operations. While not necessary in this super simple example, here’s one way to do so:

function trace_simple_power(a, n) {
let cnt = 0;
let result = simple_power(a, n);
return { result, cnt };

function simple_power(a, n) {
let result = a;
for (let i = 1; i < n; i++) {
cnt++;
result = a * result;
}
return result;
}
}

For example, it should take 6 multiplications to compute $$2^7$$:

trace_simple_power(2, 7)

### Reducing the number of steps

Here’s a recursive approach to computing , that results in far fewer computations:

function recursive_power(a, n) {
if (n == 0) {
return 1;
} else {
let x = recursive_power(a, Math.floor(n / 2));
if (n % 2 == 0) {
return x * x;
} else {
return a * x * x;
}
}
}

For example, here are 10 powers of two starting at $$n=0$$:

d3.range(10).map((n) => recursive_power(2, n))

Let’s build some traceing into this function:

function trace_recursive_power(a, n) {
let cnt = 0;

let result = power(a, n);
return { a, n, result, cnt };

function power(a, n) {
if (n == 0) {
return 1;
} else if (n == 1) {
return a;
} else {
let x = power(a, Math.floor(n / 2));
if (n % 2 == 0) {
cnt = cnt + 1;
return x * x;
} else {
cnt = cnt + 2;
return a * x * x;
}
}
}
}

For example, here’s how many multiplications are used to compute the first 20 non-negative powers of 2:

d3.range(20).map((n) => trace_recursive_power(2, n).cnt)

Hmm… looks a little complicated. Let’s plot the number of steps required to compute $$a^n$$ as a function of $$n$$:

Looks like the number of steps required is $$\log_2(n)$$ when $$n$$ is a power of $$2$$, it’s more complicated but less than twice that value when $$n$$ is one less than a power of $$2$$ and somewhere in between when $$n$$ is somewhere in between.

Most importantly, the number of steps required is far less than $$n-1$$ as $$n$$ grows.

## Double loop counts

Here’s a simple function that counts number of times through a double loop:

function count_ops(n) {
let cnt = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// Do something symmetric in i and j
cnt++;
}
}
return cnt;
}

Let’s try it for the first 16 integers:

d3.range(16).map((n) => count_ops(n))

Hmm… Those numbers look familiar. In fact, we see the positive integers in that list along the second diagonal of Pascal’s triangle:

That suggests that these numbers are exactly ${{n}\choose{2}}.$