Algorithms And Sizes Of Instances

Recent changes

Table of contents

Links to this page

FRONT PAGE / INDEX

Subscribe!

My latest posts can be found here:

Colins Blog

Previous blog posts:

Additionally, some earlier writings:

I'm deliberately moving slowly and carefully here, trying not to do too much all at once. While the ideas here all seem to be quite straight-forward, we'll hit some tricky concepts quite soon.

In the last post, Introducing Time Complexity, we look at what we mean by a "Problem", and by an "Instance" of a problem. To recap:

A "Problem" is a set of instances.
An "Instance" is a Challenge/Response pair.

If it were simply a case of memorising all the answers then there would, perhaps, not be much of interest going on here. But it's not like that (and you probably never thought it was).

No, for each challenge, we need a way of working out what the response should be. Such a method is called an "Algorithm" for that problem. So for the problem MUL, an instance is a pair of numbers, and the desired response is the product of those two numbers. So "23, 31" is an instance of MUL, and the response on the other side of the card would be 713. We need a way to compute that.

So let's think carefully about algorithms.

Setting the scene with addition

We'll start with some school arithmetic. We learn how to add two numbers that each have a single digit. What is 3 plus 5? What is 4 plus 9? We learn these single digit sums, and if we forget the answer we can just count up on our fingers and toes.

In case you're wondering, a numeral is a symbol or name that stands for a number. The number is an idea, the numeral is how we write it.
But when we're given bigger numbers to add together, we run out of fingers and toes, and we are forced to use marks on paper. We can use tally marks, but when you have 1643 sheep it's a bit tedious to have to put a mark for each one. It's better to have the numerals, and then we want to be able to do arithmetic.

So we learn long addition. (No, I'm not going to talk about long division!) We learn the process of writing out the two numbers, one above the other, and we add them in columns a digit at a time. If the total in a column is more than 9 then a "carry" spills over to the next column, and so on.

It's pretty clear that bigger numbers take longer to add, simply because there is more to do. Twice the number of digits, twice the time taken. You might wonder if there would be a faster way to do this, a question we will return to time and time again, but since we have to look at every digit it seems reasonable that, broadly speaking, we can't do better.

We could ask about using binary instead of decimal, or base 8, or base 60 (as the Babylonians did), and in fact if you've remembered all of your base 60 single digit sums, then because the numbers are shorter in base 60 it will take less time. But it's still the case that twice the digits will take twice the time.

Detail: The exact time taken depends on the number of carries. To take that into account we always talk about worst case timings, and the timings are considered to be "upper bounds."
A brief note about notation - I will sometimes use a "centre dot" to represent multiplication, as I have done here, sometimes use a "lower dot," sometimes use a "times" sign, and sometimes not have any symbol at all, using juxtaposition. It should, in each case, be unambiguous that I'm performing a multiplication, and my choice will largely be driven by aesthetics, although occasionally the need for clarity and explicitness will override that. However, if you feel strongly enough about this I invite you to email me to discuss it.
Similarly, if we do it in binary each individual column might be quicker, but on average writing a number in binary takes 3 and a bit times as many digits as it does in base 10, so there will be three and a bit times as many columns to add up. But it's still the case that twice the digits will take twice the time.

So the time taken to perform the addition is some constant times the number of digits. The exact constant will be different for different bases, etc, but it will still be:

$T=c{\cdot}S$

where $T$ is the time taken, and $S$ is the size (number of digits) of the numbers involved.

We say that the time taken is a linear function of the size of the input numbers, where the "size" of the input numbers is not their value, it's the number of digits needed to write them down.

So, to summarise:

A Problem is a collection of Instances;
An Instance is a Challenge/Response pair;
An Algorithm for a Problem is a process which, when given a Challenge, will compute the correct Response;
The Size of an instance is how many symbols are required to write down the Challenge.