Algorithms And Sizes Of Instances 


My latest posts can be found here: Previous blog posts:
Additionally, some earlier writings: 
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 additionWe'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.
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.
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:
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:
Send us a comment ...

Quotation from Tim BernersLee 