My latest posts can be
Previous blog posts:
Additionally, some earlier writings:
The story so far ...
So we have:
There are a few fuzzy bits here, and nailing them down gives us an
important concept. So let's take a specific example: ADD.
- 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;
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.
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.
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:
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
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
We read the digits in the right-most 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
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 left-most 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
So for each column, we have to do this:
Then for each column we read from right to left and do this;
- Read the two digits;
- Add the two digits;
- Write the sum;
- 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;
So the maximum amount of work we need to do for each column is:
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. |
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:
- 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);
For every column.
- Four reads;
- two additions;
- one test;
- three writes.
Using this algorithm.
But we can do better. We can devise an algorithm that takes:
I'll leave the diligent reader to work on that. We are assuming that
you can hold two numbers "in hand" as you work.
- Three reads;
- two additions;
- one test;
- two writes.
But here's the thing:
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.
- If our instance has twice as many columns,
- each algorithm will have to do twice as much work.
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
Call this function $T_1$.
- Size of instance (in some units)
- -> Upper bound for time taken (in some units)
Take another algorithm and compute its function. Call that $T_2$.
And here is a fundamental concept:
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.
So for a given algorithm, do this:
- 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
- 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;
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".
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
We'll explore this further, with examples, in the next post.
Send us a comment ...