Comparing Algorithms and Functions

Overview

Recall questions on how algorithms are compared, why problem size is the key issue, why timing is unreliable, and on functions and permutations.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   How are algorithms compared?

   Model answer

   Algorithms are set against one another by describing the complexity of each as a function of the problem size — a statement of how the time or memory required grows as the quantity of data grows. Comparison then means comparing those growth rates rather than individual timings, which is what keeps the judgement independent of the machine: an O(n log n) sort will eventually beat an O(n²) sort on large inputs whatever hardware each is run on.

2. 2

   Why is the size of the problem the key issue when comparing algorithms?

   Model answer

   Because it is the growth with size, not the cost on one input, that decides which algorithm is usable. An algorithm whose work grows in proportion to n and one whose work grows in proportion to n² may be indistinguishable at n = 10, where the counts are 10 and 100, but at n = 1,000,000 they are a million and a million million. Whatever advantage a slower-growing algorithm gives up in constant overheads is eventually swamped by that difference, so once the problem size is large enough the growth function decides the outcome.

3. 3

   Why is comparing two algorithms by timing them on one computer an unreliable comparison?

   Model answer

   The timing measures the machine, the language, the compiler, the state of the cache and the particular input as much as it measures the algorithm. Run the same pair on a faster processor and both times fall, which tells you nothing new about the algorithms. Faster hardware multiplies the running time by a constant, whereas the way the work grows with problem size is a property of the algorithm itself and does not change when the machine does.

4. 4

   What is meant by saying one algorithm is more efficient time-wise than another?

   Model answer

   It means that as the problem size grows it performs fewer of the operations that dominate the running time, so it finishes sooner. Binary search is more efficient time-wise than linear search on a sorted, randomly accessible list: to search a million items, linear search may examine up to a million of them, whereas binary search examines about twenty, because each comparison halves the range left to search.

5. 5

   What is meant by saying one algorithm is more efficient space-wise than another?

   Model answer

   It means it uses less memory to solve the same problem, counting the working storage it needs in addition to the input. Bubble sort is more efficient space-wise than merge sort, because it sorts within the original array and needs only a couple of extra variables, whereas merge sort needs additional storage proportional to the number of items to hold the merged sub-lists.

6. 6

   Give an example of a trade-off between time efficiency and space efficiency.

   Model answer

   A hash table storing records for lookup by key uses considerably more memory than a simple array of the same records, because the table is deliberately kept partly empty to reduce collisions. In exchange, a lookup takes constant time on average instead of having to search through the array. The extra memory has bought speed. The same trade appears whenever results are cached or an index is built: storing pre-computed answers costs space and saves time, recomputing them each time costs time and saves space.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.