Comparison of the Complexity of Algorithms (OCR A-Level Computer Science): Flashcards

Minimum number of operations

Expected performance across all possible inputs

Maximum number of operations

$O(n)$

$O(\log n)$

Requires sorted data

$O(n)$

$O(n \log n)$

$O(n^2)$

Pivot is smallest or largest element repeatedly

$O(n^2)$

$O(n)$

Data already sorted, only one pass needed

Input characteristics: sorted, unsorted, reversed, random data

Requires significant extra memory