Discuss at length the measurement of the time and space consumed by an algorithm in order to determine its efficiency.

Question

What will be an ideal response?

Answer 1

To determine whether an algorithm is efficient, space efficiency can be judged by the amount of information the algorithm must store in the computer's memory to do its job, in addition to the initial data on which the algorithm is operating. If it uses only a few extra memory locations while processing the input data, the algorithm is relatively space efficient. If the algorithm requires almost as much additional storage as the input data itself takes up, or even more, then it is relatively space inefficient. To measure the time efficiency of an algorithm, consider a sequential search algorithm that looks up a name in a telephone directory where the names are not arranged in alphabetical order. How about running the algorithm on a real computer and timing it to see how many seconds (or maybe what small fraction of a second) it takes to find a name or announce that the name is not present? The difficulty with this approach is that there are three factors involved, each of which can affect the answer to such a degree as to make whatever number of seconds we come up with rather meaningless.

1. On which computer will we run the algorithm? Shall we use a modest laptop or a supercomputer capable of doing many trillions of calculations per second?
2. Which telephone book (list of names) will we use: New York City or Yeehaw Junction, Florida?
3. What name will we try to find? What if we pick a name that happens to be first in the list? What if it happens to be last in the list?

Simply timing the running of an algorithm is more likely to reflect machine speed or variations in input data than the efficiency (or lack thereof) of the algorithm itself. This is not to say that you can't obtain meaningful information by timing an algorithm. For example, using the same input data (searching for Karlenski, say, in the New York City phone book) and timing the algorithm on different machines gives a comparison of machine speeds because the task is identical. Using the same machine and the same list of names, but searching for different names, gives an indication of how the choice of NAME affects the algorithm's running time on that particular machine. This type of comparative timing is called benchmarking. Benchmarks are useful for rating one machine against another and for rating how sensitive a particular algorithm is with respect to variations in input on one particular machine. However, what we mean by an algorithm's time efficiency is an indication of the amount of "work" required by the algorithm itself. It is a measure of the inherent efficiency of the method, independent of the speed of the machine on which it executes or the specific input data being processed. Is the amount of work an algorithm does the same as the number of instructions it executes? Not all instructions do the same things, so perhaps they should not all be "counted" equally. Some instructions are carrying out work that is fundamental to the way the algorithm operates, whereas other instructions are carrying out peripheral tasks that must be done in support of the fundamental work. To measure time efficiency, we identify the fundamental unit (or units) of work of an algorithm and count how many times the work unit is executed.