← Computer Science syllabus

EnglandComputer Science

2.3 Algorithms

4 dot points across 4 inquiry questions. Click any dot point for a focused answer with worked past exam questions where available.

How do we measure and compare the efficiency of algorithms using Big-O notation?

Big-O notation for time and space complexity: the constant, logarithmic, linear, linearithmic, polynomial and exponential complexity classes, how to determine the Big-O of an algorithm, and using it to compare and judge the suitability of algorithms.
An OCR H446 answer on Big-O notation: the constant, logarithmic, linear, linearithmic, polynomial and exponential complexity classes for time and space, how to determine an algorithm's Big-O, and using it to compare algorithms and judge their suitability.
14 min answer →

How do we traverse a graph or tree, and how do Dijkstra's algorithm and A* find a shortest path?

Graph and tree traversal: breadth-first and depth-first traversal of a graph, the pre-order, in-order and post-order traversal of a binary tree, and the shortest-path algorithms Dijkstra's algorithm and A* search.
An OCR H446 answer on traversal and shortest-path algorithms: breadth-first and depth-first graph traversal, the pre-order, in-order and post-order traversal of a binary tree, and how Dijkstra's algorithm and A* search find a shortest path.
14 min answer →

How do linear and binary search work, and why is binary search so much faster on a sorted list?

Searching algorithms: linear search, binary search and binary tree search, how each works with a trace, the precondition for binary search, and their time complexity in Big-O notation.
An OCR H446 answer on searching algorithms: how linear search, binary search and binary tree search work with worked traces, the requirement that binary search needs a sorted list, and the time complexity of each in Big-O notation.
14 min answer →

How do bubble, insertion, merge and quick sort order a list, and why are the divide-and-conquer sorts faster?

Sorting algorithms: bubble sort, insertion sort, merge sort and quick sort, how each works with a trace, and their time complexity in Big-O notation including best, average and worst cases.
An OCR H446 answer on sorting algorithms: how bubble sort, insertion sort, merge sort and quick sort order a list with worked traces, and their time complexity in Big-O notation including the difference between the quadratic and the divide-and-conquer sorts.
14 min answer →