6.3 ALGORITHM EFFICIENCY AND 'BIG-O' EXPRESSION

The efficiency of a computer program may mean a number of things. It may be the number of lines of code, the amount of memory or backing storage needed, or the time taken to execute the program. When seeking to increase efficiency, there is often a trade-off between factors such as the amount of memory needed and the speed of execution. Algorithm efficiency is itself a major field of interest and we shall do no more than introduce the topic in this section, providing an estimate of efficiency for the algorithms developed.

Common operations involve searching for items in a data set or sorting them into order (see Chapter 8), both of which involve comparing pairs of values. For all such operations, the execution time depends upon the size of the data set and the number of comparisons made. The method used for the operation is also of great significance, and this is the case for linear search versus binary search.