Computational Complexity

Share this: Google+
< Contents | Previous | Next >

Software is the computer program that makes your electronic hardware useful. Inside the software you have algorithm that will turn the data that you inputted to the software into some results output of the software. The data input can be stored inside the computer (such as text file, xml file, or a database) or interact with the user (that you need to type in, click using your mouse or touch screen, talk to the microphone, or get from your camera, and so on). The user of computer program are not necessarily human, it can be another machine or distributed computers over the network. Similarly the output of a software can be channeled into various devices such computer screen, headphone, game device that vibrate or simply an electrical input into other hardware and so on.

In the raw material, a software is just a computer code that can be run on a machine. In the core of computer code, there are algorithms that make that software run efficiently. Algorithm is the procedure to conduct specific sequential actions to solve a problem. Algorithms are the soul of each software. Putting bad algorithms into software is just are similar to put bad spirit into the corpse. Without its soul, the corpse of the software will just like zombies, the walking dead.

The better algorithm that you put into the computer code, the more effective and efficient the software. The effectiveness of an algorithm depends on its role and purpose as a part of the whole software. Effectiveness is hardly measurable. On the other hand, the efficiency of algorithms is measurable. Ideally, efficient algorithms will make faster software, consume less computer memory space and less hard disk space (if you use virtual memory that utilize your hard disk as computer memory).

Not all software are created equal. For the same purpose, some software are much more efficient than the others. How do we measure efficiency of a software? Of course, you can run the software and measure the running time, monitor the usage of memory space. However, that kind monitoring the run time, memory space requires that the software has been build and it can run.

To make the matter worst, the result of monitoring the run time and memory space is only correct for one specific computer. If you run it in another computer, you need to do the same monitoring again and you would probably get significantly different results. In other words, monitoring the run time and memory space is hardware dependent. Aside that, the performance of the code may also dependent on the operating systems (such as Windows, Linux, iOS), programing languages (for instance, if you code it in C or Assembly it would probably run 2 to 10 times much faster than if you code it in PHP or Python) and compilers (i.e. C has many type of compilers) and programmer’s ability (i.e. you and your friends may have code it differently depending on the programming experience. A higher level programmers could have productivities of about 80 times more than a normal programmer. See my side note).

Imagine if you need to code all the possible algorithms that serve the same purpose and try to run them all and measure the run time and space they need on all different computers, different operating system. The monitoring process would take weeks or months just to compare a single algorithm on a single computer. That is a waste of our precious time.

The efficiency of an algorithm is called computational complexity. Fortunately, we don’t need to do such run time comparison anymore (except for a specific machine) because the mathematics of computational complexity can help you.

Since the core of any software is the algorithms behind it, is it possible to estimate the run time and the usage of space of an algorithm before we even code it and independent of the hardware? If we can measure the efficiency of algorithms, we can compare various algorithms for the same purposes and then we can select the best one without the need to know what computer we will use to run this code. All of these comparisons of algorithms can be done without typing a single code and without the need to run the computer code in the real computer. Isn’t that awesome?

Read on and we will discuss how to measure the complexity in the next section.

< Contents | Previous | Next >