Comparing algorithms and choosing one for a task

Overview

Recall questions on choosing between algorithms by complexity, why constants can let a slower-growing algorithm lose, hybrid sorts, memory and data size, sorting on embedded devices and servers, sorted versus unsorted searching, and Dijkstra's versus A*.

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

   Two algorithms solve the same problem, one O(n log n) and one O(n squared). Which would you choose for a list of a million items, and why?

   Model answer

   The O(n log n) one. At a million items log n is about 20, so the work is of the order of twenty million operations, whereas n squared is of the order of a million million. The gap widens as the data grows, so for large data the complexity class matters far more than any other consideration.

2. 2

   Big O ignores constants. Explain why that means an O(n squared) algorithm can still beat an O(n log n) one.

   Model answer

   Big O describes how the cost grows, not how large it is. An O(n squared) algorithm with a very small constant cost per operation, such as insertion sort, can do less real work than an O(n log n) algorithm that has heavy overheads such as recursive calls and copying into temporary arrays. Below a crossover point of a few dozen items the simpler algorithm wins; above it the better complexity always takes over.

3. 3

   Give a practical consequence of that crossover point.

   Model answer

   Real sorting implementations are often hybrids: they use merge sort or quick sort to break the data down, then switch to insertion sort once a sublist falls below a threshold of roughly ten to twenty items, because insertion sort finishes those small pieces with less overhead.

4. 4

   Besides the number of operations, what else should you weigh when choosing an algorithm for a task?

   Model answer

   How much memory it needs and how much is available, the size of the data set now and in the future, whether the data is already partly sorted, whether the data arrives all at once or item by item, whether equal items must keep their original order, and how complicated the algorithm is to implement correctly and maintain.

5. 5

   Why is complexity a fairer basis for comparing two algorithms than the time they take on one test?

   Model answer

   A single test result depends on the hardware, the language and that particular data set, and it says nothing about behaviour on data ten times larger. Complexity describes the growth of the algorithm itself, so a comparison made on complexity holds on any machine and predicts what happens as the data set grows.

6. 6

   An embedded device has very little spare memory and must sort a list of about 30 readings. Which of merge sort and insertion sort would you choose, and why?

   Model answer

   Insertion sort. It sorts in place using O(1) extra memory, whereas merge sort needs O(n) additional storage the device may not have. With only about 30 items the O(n squared) growth costs very little in absolute terms, so the memory constraint decides it.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.