Comparing Algorithms

Note: If you have already covered our course Data Structures in C++: An Interview Refresher you may skip this chapter, since a chapter on Algorithmic Complexity Measures was a part of the said course, too.

Introduction #

There are typically 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 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 #

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 made 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, algorithms being compared

...