Comparing Algorithms

Introduction

There are typically several different algorithms used to solve a given computational problem. It is natural, then, to compare these alternatives. But how do you know if algorithm A is better than algorithm B?

Important Criteria: Time and space

One important factor that determines the “effectiveness” of an algorithm is the amount of time that the algorithm will take to solve a given problem. If algorithm A takes less time to solve the same problem than algorithm B, then algorithm A is considered better.

Another important factor in comparing two algorithms is the amount of memory required to solve a given problem. The algorithm that requires less memory is considered better.

Comparing execution time

The remainder of this lesson will focus on the first factor, i.e., execution time. How do you compare the execution time of two algorithms?

Experimental evaluation

Well, you could implement the two algorithms and run them on a computer while measuring the execution time. The algorithm with less execution time wins. But one thing is certain: this comparison must be made in a fair manner. Let’s try to understand this better:

• An algorithm might take longer to run on an input of greater size. Thus, algorithms that are being compared must be tested on the same input size. But that’s not all. Due to the presence of conditional statements, for a given input size, even the same algorithm’s running time may vary with the actual input given to it. This means that the algorithms that are being compared must be tested on the same input. Since one algorithm may be disadvantaged over another for a specific input, you must test the algorithms exhaustively on all possible input values. But this is not possible.
• The algorithms that are being compared must first be implemented. What if the programmer comes up with a better implementation of one algorithm than the other? What if the compiler optimizes one algorithm more than it does the other? There is so much that can compromise fairness at this stage.
• The programs implementing the two algorithms must be tested on exactly the same hardware and software environment. As far fetched as it may seem, you could assign a single machine for all scientists to test their algorithms. Even if you did, the task scheduling in modern day operating systems involves a lot of randomness. What if the program corresponding to “the best” algorithm encounters an excessive number of hardware interrupts? It is impossible to guarantee the same hardware/software environment to ensure a fair comparison.

Analytical evaluation

The above list highlights some factors that make fair experimental evaluation of algorithms impossible. Instead, you are forced to make an analytical/theoretical comparison. The two key points that you should hold on to from the previous discussion is that you must compare algorithms for the same input size, and consider all possible inputs of the given size. Here is how it is done.

Assume that a hypothetical computer on which some primitive operations are executed in a constant amount of time. Consider a specific input size, $n$. Then count the number of primitive operations executed by an algorithm for a given input. The algorithm that results in fewer primitive operations is considered better.

But what constitutes a primitive operation? You can think of these as simple operations that are typically implemented as processor instructions. These operations include assignments to a variable or array index, reading from a variable or array index, comparing two values, arithmetic operations, and context switch that results from a function call.

A context switch is when the control is transferred from the calling function to the called function.

What is not considered a primitive operation? While the “context switch” is a primitive operation, the function invocation as a whole is not always a single primitive operation. A function call’s cost is considered to be the sum of the primitive operations in the function body. Similarly, displaying an entire array is not a primitive operation.

The number of times conditional statements run depends on the actual input values. Sometimes a code block is executed, and sometimes it isn’t. How do you account for conditional statements? You can adopt one of three strategies: best-case analysis, average-case analysis, and worst-case analysis.

Best-case analysis

In the best-case analysis, you should consider the specific input that results in the execution of the fewest possible primitive operations. This gives you a lower bound on the execution time of that algorithm for a given input size.

Worst-case analysis

In the worst-case analysis, you should consider the specific input that results in the execution of the maximum possible primitive operations. This gives you an upper bound on the execution time of that algorithm for a given input size.

Average-case analysis

In the average-case analysis, you should try to determine the average number of primitive operations that are executed for all possible inputs of a given size. This is not as easy as it may sound to the uninitiated. In order to compute the average-case running time of an algorithm, you must know the relative frequencies of all possible inputs of a given size. You can compute the weighted average of the number of primitive operations that are executed for each input. But how can you accurately predict the distribution of inputs? If the algorithm encounters a different distribution of inputs in the field, then your analysis becomes useless.

The verdict

The best-case analysis has limited value: what if you deploy that algorithm and the best case input rarely occurs? We feel that the worst-case analysis is more useful. This is because whatever answer it gives you, algorithm A wouldn’t incur more time than that. Unless otherwise specified, your analysis in this course will be the worst-case running time.

The running time of an algorithm computed in the aforementioned way is also known as its time complexity. Another term that you will often hear is an algorithm’s space complexity. The space complexity of an algorithm is the amount of additional or auxiliary memory space that the algorithm requires. This is memory space other than the actual input itself. You will see examples of evaluating the space complexity of an algorithm later in this course.

Analyzing a simple C# program

Suppose that instead of an algorithm, you were given C# code. Here’s how you can analyze the algorithm underlying the given program. Count the number of primitive operations in the program given below: