Comparing Algorithms

Introduction

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

Important criteria: time and space

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

Another important factor to compare 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

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

Experimental evaluation

Well, we could implement the two algorithms and run them on a computer while measuring the execution time. The algorithm with less execution time wins. One thing is for sure, this comparison must be done in a fair manner. Let’s try to punch holes into this idea:

• An algorithm might take longer to run on an input of greater size. Thus, the algorithms 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 being compared must be tested on the same input. Since one algorithm may be disadvantaged over another for a specific input, we must test the algorithms exhaustively on all possible input values. This is just not possible.
• The algorithms being compared must

...