A Textbook of Data Structures and Algorithms, Volume 1

2Analysis of Algorithms

In the previous chapter, we introduced the discipline of computer science from the perspective of problem solving. It was detailed how problem solving using computers calls not only for good algorithm design but also for the appropriate use of data structures to render them efficient. This chapter discusses methods and techniques to analyze the efficiency of algorithms.

2.1. Efficiency of algorithms

When there is a problem to be solved, it is probable that several algorithms crop up for its solution, and therefore, one is at a loss to know which one is the best. This raises the question of how one decides which among the algorithms is preferable or which among them is the best.

The performance of algorithms can be measured on the scales of time and space. The former would mean looking for the fastest algorithm for the problem or that which performs its task in the minimum possible time. In this case, the performance measure is termed time complexity. The time complexity of an algorithm or a program is a function of the running time of the algorithm or program. In the case of the latter, it would mean looking for an algorithm that consumes or needs limited memory space for its execution. The performance measure in such a case is termed space complexity. The space complexity of an algorithm or a program is a function of the space needed by the algorithm or program to run to completion. However, in this book, our discussions mostly emphasize the time complexities ...