A pragmatic definition of "efficiency"

  • Describe what is meant by the efficiency of algorithms.

There are multiple ways to solve a computational problem, as we have seen with linear and binary search. Measuring their tradeoffs involves analyzing their efficiency.

Efficiency here means how an algorithm utilizes resources, namely the amount of time (and space) it uses. Moreover, we want to know how its resource consumption will scale with increasing input size.

We need to establish the vocabulary and the required mathematical machinery to talk about the efficiency of algorithms. To that end, we introduce the RAM model of computation in this chapter and asymptotic notation in the next chapter.

Resources