What Is Algorithm Analysis?
Before we dive into the subject of Algorithm Analysis, let’s get a clear understanding of what an algorithm actually is.
Whenever we want to solve a problem with a computer, we process large amounts of data. To actually make sense of this data, we need some set of rules on how we’re supposed to process it. This is where the algorithm comes in.
An algorithm is a specified set of rules/instructions that the computer will follow to solve a particular problem. In other words, we need to tell the computer how to process the data, so we can make sense of it.
This might be easier to understand with a practical example:
Let’s assume you work as a programmer, and you have to sort the data about your company’s customers. Your boss want you to sort it based on their last names. Instead of manually going through the list (which will be a full time job itself), you program a routine that compares the customers last names – and organize them in a sorted manner. That’s it – you’ve just created an algorithm, which sorts data alphabetically.
In today’s society, time is critical — and computer science is no exception. We want to process large amounts of data, and we want to do it as fast as possible. This is where algorithm analysis comes in. Whenever we come up with a new algorithm, or make use of a pre-existing one, we want to know how fast the data can be processed.
The first factor which comes to interest is of course the amount of input that must be processed. Surely, we can sort 10 elements faster than we can sort 10,000 elements. Thus, more data equals more time.
But, although the running time of an algorithm is largely dependent on the amount of input, we generally don’t focus much on this aspect. The amount of data we need to process is often out of our hands, especially with sorting algorithms. Referring to the example above, it would not make any sense to reduce the amount of input data — we need to sort all the customers, not just some of them.
Another factor which you may want to consider important, is the speed of the host machine. And although correct, this is not what algorithm analysis is about. Actually, in general, when performing algorithm analysis, we exclude external factors as the speed of the host machine, the quality of the compiler, etc.
When performing algorithm analysis, we want to evaluate the performance of an algorithm in terms of its input size. In other words, we’re evaluating how the performance of an algorithm changes according to its input size.
One naive way to perform the analysis is to measure the actual run-time of the algorithm. This can, and will, produce false results. Assuming we have two algorithms, algorithm 1 and algorithm 2:
An example of performing algorithm analysis this way, and thus producing false results, is as follows:
Let’s say we want to compare two different search algorithms, the Linear Search (the growth rate is a linear function of the input size), and the Binary Search (the growth rate is a logarithmic function of the input size). For simplicity, assume we run the algorithms on two different machines.
Clearly, the Linear Search is less efficient than the Binary Search, since the growth rate is linear, and not logarithmic. However, since we ran the algorithms on two different machines, it appeared as the linear search was faster than the binary search.
Instead of comparing the actual run-time, which will differ based on a whole lot of external factors, we want to use something called Asymptotic Analysis.
