Who cares?

Well, apart from the obvious reasons as to why we would want to know how much time and space an algorithm takes, what's really the point? This is a question that a lot of people have when they are confronted with the theoretical concepts.

You might think that computers are fast enough, and that we can simply keep pumping more Giga-hertz to make the world go 'round. This is simply not true. In fact, it is easy to prove that with our currently technology in computing, it is almost impossible to solve a these problems even if we use every atom in the universe to build our physical machine.

From a mathematical point of view, analysis of algorithms is an interest in itself. But complexity analysis is simply more than an exercise of the intellect. Most problems in the world are hard - hard for computers. And understanding quantities like space and time can allow us to create algorithms which are approximations - or we can try and trade space for time. That is, we can often re-design an equivalent algorithm which will in fact use more space but take less time.

These problems are ones which can only be solved with complexity analysis. They cannot be solved simply by blindly adding more threads. They are deeper than most design issues in software engineering - the only way to untangle them and hope to find a solution is to perform rigorous mathematical analysis.

There is an economical motivation behind complexity analysis too. I remember my lecturer Prof. John Crossley (Monash University) explain - ``If your employer asks you to solve a problem, and you can prove that it is NP-HARD - then you know it's impossible to solve it in our lifetimes.'' Well, something to that effect.

Menaka Lashitha Bandara 2005-04-18