OCR A-Level Computer Science Algorithms and complexity overview quiz quiz

$O(n)$

$O(1)$

$O(\log n)$

$O(n^2)$

checks every single item in the list once, from the first element through to the last

halves the remaining items at each comparison

sorts the entire list first and then reads off the value sitting in the middle position

uses a queue to hold the items still waiting to be examined during the search

Merge sort

A binary search

Bubble sort

Dijkstra's algorithm

comparing adjacent items and swapping them whenever they are found to be out of order

choosing a pivot element and partitioning the list into items below and above that pivot

checking each item in turn against the target until the correct value is finally located

splitting the list into halves recursively, then merging sorted sublists

$O(n^2)$

$O(\log n)$

$O(n)$

$O(n \log n)$

A stack

A queue

A binary tree

A hash table

Pre-order

Post-order

In-order

Level-order

all equal to one another, so that every edge carries the same weight

negative, so that longer paths can reduce the total distance travelled

fractional values strictly between zero and one, never whole numbers

non-negative

It adds a heuristic estimate of the remaining distance to the goal

It ignores the edge weights entirely and simply counts the number of edges along each path

It only works on unweighted graphs, where every edge between two nodes counts as one step

It uses a stack of nodes to explore instead of tracking the distances found so far

$O(3n^2)$

$O(n^2)$

$O(n)$

$O(n^2 + n)$

$O(n^2)$

$O(2^n)$

$O(1)$

$O(n)$

$O(n)$

$O(2n)$

$O(\log n)$

$O(n^2)$