Introducing Time Complexity

   
Recent changes
Table of contents
Links to this page
FRONT PAGE / INDEX

Subscribe!
@ColinTheMathmo

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

The Initial Ideas ...

A short time ago I was chatting about and working on some puzzles with a friend, and casually mentioned something about how the time complexity of this particular problem behaved. What then transpired was that my friend didn't know anything about how the whole "Time Complexity" thing worked, and didn't understand about $\mathcal{P}$ versus $\mathcal{NP}$ and similar concepts.

For normal people that wouldn't perhaps be so surprising, but this friend is an outstandingly good mathematician, so I was caught out somewhat. But two or three years ago I'd been writing an article, or post, or book, or something, and never got round to "publishing" it in any form.

So here it is, in, what I hope, will be bite-sized, accessible chunks. I would really appreciate feedback on this. Although I'm posting it as a series of pages on my bloggy thing, I intend to come back and refine them as people point out errors, or places where the explanation could be improved. I'd love that - doing so would, to some extent, have the effect of "crowd sourcing" the posts/pages to become a decent resource.

And so we begin ...

What is "A Problem?"

There are many connected concepts, and in discussing these ideas with people I've found that many of them have the basic ideas, but not the technical understanding. And that's perfectly reasonable, because most "popular writing" doesn't actually give the technical definitions. And to some extent I'll be walking a rather fine line here as well, since I don't have the background to go into the deep technical details, but I'll try to be interesting and informative.

I'm going to talk about X different problems as specific examples, where X may well change. To start with, here are the "problems" (yes, that will become a technical term) I'll be using:

  • Squaring integers ( SQR );

  • Multiplication of integers ( MUL );

  • Factoring integers ( FAC );

  • Hamilton Cycle ( HAM );

  • Graph 3-Colouring ( G3C );

  • Satisfiability ( SAT ).

OK, so to start with, X=6.

Some of these may not be familiar to you, so we'll start with one that shouldn't take too much explaining: SQR.

So here's the setup. I have a set of 3x5 cards, and on one side is an integer. That's the side that you'll get shown, and on the other side is the square of that integer. So I might choose a card and hold it up to you, revealing the number "23". Your job, the problem you face, is then to tell me what's on the other side.

Soon we will talk about the process of deriving the response to each challenge. We do that by using an algorithm, and "Time Complexity" is analysing how long that algorithm will take.

That's where we're going with this - understanding that analysis. But that's some distance away yet, we need some groundwork first.

On this occasion what's on the other side will be "529", which you can easily determine by putting 23 into a calculator and pressing the right keys in the right order, or, if you're practised at this sort of thing, working it out in your head.

But the idea is that one can "compute" what's on the other side.

So one "instance" of the problem SQR is the number "23".

So here's a summary of the important terms (and don't worry, we'll go over these again):

  • An "Instance" is a specific Challenge/Response pair.
    • We can think of this as being on an 3x5 card, with the challenge on one side, and the response being what you need to produce.

  • A "Problem" is a set of instances.

So the problem SQR is a drawer full of 3x5 cards (which we call instances), each with a positive integer on the front and the square of that positive integer on the back.

Looking forward ...

I've started with SQR because it's easy to describe, and it feels fairly familiar and straight-forward, whereas some of the other problems are unfamiliar, obviously complicated, and it will come as no surprise that there are some tricky questions about them.

What may surprise you is that we are already on the verge of some research level maths into unanswered questions.


<<<< Prev <<<<
The Linear Frog
:
>>>> Next >>>>
Algorithms And Sizes Of Instances ...


https://mathstodon.xyz/@ColinTheMathmo You can follow me on Mathstodon.



Of course, you can also
follow me on twitter:

@ColinTheMathmo


Send us a comment ...

You can send us a message here. It doesn't get published, it just sends us an email, and is an easy way to ask any questions, or make any comments, without having to send a separate email. So just fill in the boxes and then

Your name :
Email :
Message :


Contents

 

Links on this page

 
Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.

Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!