Subscribe!
My latest posts can be
found here:
Previous blog posts:
Additionally, some earlier writings:

The story so far ...
So we have:
 A Problem is a collection of instances;
 An Instance is a Challenge/Response pair;
 The size of an instance is how many glyphs it takes to specify it;
 An Algorithm (for a problem) is a process or recipe that takes a Challenge and produces the correct Response;
There are a few fuzzy bits here, and nailing them down gives us an
important concept. So let's take a specific example: ADD.
This section gets into some rather messy details. You
don't need to understand it all, but if you read slowly and
carefully it should all make sense, and convince you that you
really don't want to be doing this all the time.
And that's actually the point. We get to a stage here where we
can see that the messy bits are, in the larger picture, irrelevant.
But unless we get our hands dirty first we can't really see what
the fuss is. When we have got our hands dirty we can see why
the concept that emerges is so powerful.
Well, maybe you won't see it yet, it will take a little while.

Getting to some messy details.
In the ADD problem a Challenge consists of two numbers, and the
Response is the sum. So on one side of an Instance card we might
have the Challenge "24 + 67" and the correct Response would be
"91". Another Challenge might be "12 + 56" and the Response
would be "68".
But if we're only allowed to add two digits together at a time, if
that's a basic "step" in our process, these two results would take
a different amount of time to compute. Why? Because the first one
has a carry, and dealing with that takes time.

In detail, let's look at "12+56":
We start by adding the 2 and the 6, and that's something we can do
in one step, so we write down 8:


But that's not really one step. We have to read the 2, read the
6, add them together, and write down the answer. So it's two reads,
one addition, and one write.
Then we add the 1 to the 5, and that can also be done in two reads,
one addition, and one write.

Now we're done, and we have our answer: 68. That took exactly
four read operations, two additions of single digits, and two write
operations.

Now let's do the other sum. Be warned! I'm not quite going to do
this the way you might be familiar with. The method I'll use here
is very similar, provably equivalent, but slightly different. Don't
panic.

We read the digits in the rightmost column, add them, and write down
the result. But immediately we see that there's a problem. The result
isn't a single digit, and we need to have just a single digit in that
place.
What we do now is where we deviate from what you might be familiar
with, but bear with me. We'll write down the 11, and then come back
and fix it later.


We work on the next column, the leftmost column now. Again we have
two reads, one add, and one write. So we've done the same as before,
and now we need to fix the minor problem with the "11" in the result.
We can work across the last row, the answer row, working right to
left, and we check each number. If it's 10 or more then we split it,
leaving behind the digit and carrying the "1" with us. This requires
an extra read for each digit in the answer, and an extra "add" and
"write" for each carry.
So the number of atomic operations performed depends on exactly how
many carries there are (and to be completely honest, exactly how we
count them), but we know that we can't have more than one carry for
each column.
So for each column, we have to do this:
 Read the two digits;
 Add the two digits;
 Write the sum;
Then for each column we read from right to left and do this;
 Check if the sum is bigger than 9;
 (at worst this will be true every time)
 Write the digit;
 Add the carry to the result in the next column;
I did warn you that this would get messy. But you don't need
to read all the details unless you want to, all you need to do is see
that we are counting how many steps we need to perform when we break
this down into a detailed process. 
So the maximum amount of work we need to do for each column is:
 Two reads;
 One addition;
 One write;
 One read;
 One test;
 One write (of the digits);
 One read (of the next number);
 One addition (of the carry to that number);
 One write (of the next number);
Clearly we can improve this a little, because several times we have
written a result, only to read it again. However, that's the maximum
amount of work we have to do:
 Four reads;
 two additions;
 one test;
 three writes.
For every column.
Using this algorithm.
But we can do better. We can devise an algorithm that takes:
 Three reads;
 two additions;
 one test;
 two writes.
I'll leave the diligent reader to work on that. We are assuming that
you can hold two numbers "in hand" as you work.
But here's the thing:
 If our instance has twice as many columns,
 each algorithm will have to do twice as much work.
The second algorithm is faster, yes, but in relative terms it's
always faster by the same amount. It's always 10% faster, or 15%
faster, or whatever it is, but it's always a constant factor faster.
And that might matter, but it does tell us that there's nothing
radically better about the second algorithm.
And therein lies an important concept.
Given a problem, and an algorithm, for each size of instance, compute
a "worst case" amount of time the algorithm will take. This gives us
a function:
 Size of instance (in some units)
 > Upper bound for time taken (in some units)
Call this function $T_1$.
Take another algorithm and compute its function. Call that $T_2$.
This is the magic, this is the important step.
This is not obvious!
We will come back to this to explore further what it says,
and what it means.

And here is a fundamental concept:
 Suppose there is a constant, $c$, that has this property:
 As the sizes of the instances grow without bound,
 $cT_1$ is always "close to" $T_2$.
 In that case we say that the two algorithms have the same
"Time Complexity".
So for a given algorithm, do this:
 For each size of instance,
 compute an upper bound for how long it will take;
 Plot that on a chart,
 instance size across the bottom,
 time up the side;
WARNING
This is not strictly true, and I'll come back to the more complete
and precise definition later. For now, it gives the right sense of
what's happening.

If you do this for two different algorithms and the results are, apart
from a scaling factor, pretty much the same, then the algorithms are
said to have the same "Time Complexity".
We'll explore this further, with examples, in the next post.
Send us a comment ...
