The suitability of different algorithms for a given task and data set, in terms of execution time and space

The suitability of different algorithms for a given task and data set, in terms of execution time and space.

2.3.1 Algorithms

Algorithms — Note 2 of 6

Candidates need to understand that a task can have a range of solutions that differ in execution time and memory use. Candidates need to be able to compare algorithms against one or more data sets and judge which is more efficient in terms of speed and/or memory.

What you need to know

There is usually more than one algorithm for a task. The most suitable depends on the size and nature of the data and on whether execution time or memory use matters more.

What to know

The size of the data set matters: a simple O(n²) algorithm may be fine for 10 items but far too slow for 1,000,000.
The state of the data matters: insertion sort is very fast on nearly sorted data; binary search needs sorted data.
There is often a trade-off between time and space: merge sort is fast but needs extra memory; bubble and insertion sort need very little extra memory but are slower on large data.

Key terms

Time complexity: How the time taken by an algorithm grows as the size of the input grows.
Space complexity: How the amount of memory needed by an algorithm grows as the size of the input grows.

Exam technique

Tip:Justify your choice by referring to BOTH the algorithm's characteristics and the specific data set in the question.

← Previous noteAnalysis and design of algorithms for a given situation2.3.1 Algorithms Next note →Measures and methods to determine efficiency, Big O notation2.3.1 Algorithms

Back to Algorithms