Introduction to Complexity

When we attempt to perform a task in real life, whether it be driving a car or building a house, we often talk about how difficult it is to perform that task. For instance, building a house in some sense will be often much harder than driving a car.

We know that some programs run slower than others, while others require more memory. Typically, a program is simply composed of various algorithms. And typically, the two attributes described above - space and time, are the two quantities we can associate with any algorithm.

Now, computers as pieces of hardware are boring. This is a lesson in theoretical computer science - and in theoretical computer science, we abstract away results from physical machines. This is natural - in fact, a lot of the theory did actually precede the application. We want to talk about the space and time of algorithms themselves, not of the machines on which they are implemented. Thus, we have to get back to pencil and paper, and analyse the algorithm as a mathematical object.

We use the word complexity to describe and measure quantities to do with algorithms including, but not restricted to, things like space and time. The meaning of complexity is a bit of a mystery. We actually haven't developed an abstract theory of complexity that is well understood and accepted.

A disclaimer before we begin: This is very introductory material to a formal treatment of complexity. The reader should understand that in order to understand this area more rigorously, they should consult the references which I have listed.

Menaka Lashitha Bandara 2005-04-18