Constant Differences

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:

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.

 
    1   2
    5   6 +
  ========

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:

 
    1   2
    5   6 +
  =========
        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.

 
    1   2
    5   6 +
  =========
    6   8

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.

 
    2   4
    6   7 +
  =========

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 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.

 
    2   4
    6   7 +
  =========
       11

2 4 6 7 + ========= 8 11

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 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.

<<<< Prev <<<<

Algorithms And Sizes Of Instances

>>>> Next >>>>

Introducing Big Oh ...