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

Minimum number of operations

Maximum number of operations

$O(n)$

$O(\log n)$

Data must be sorted

$O(n)$

$O(n^2)$

Pivot is smallest/largest repeatedly

$O(n \log n)$

$O(n^2)$

Uses significant extra memory

Average case = worst case