Exam Board:
OCR A-Level
Specification:
Computer Science H446
3.1a - 3.1d - Algorithm Complexity
Watch on YouTube:
Pseudocode
Procedural programming
Big O notation
Algorithm complexity
Pseudocode
Pseudocode is a simplified, language-independent way of writing algorithms that looks like programming but uses plain English to describe the steps clearly without worrying about exact syntax.
The OCR A-Level Computer Science course uses a form of pseudocode unique to the exam board called 'OCR exam reference language' that all code in exams will be written in.
OCR exam reference language uses closing commands such as endif for an if statement and endwhile for a while loop. It also uses the word then instead of a colon like in Python.
Procedural Language
A procedural language, such as Python or Java, is a programming language that structures programs as sequences of step-by-step instructions grouped into procedures or functions.
It focuses on breaking tasks into smaller, reusable blocks of code that operate on data, making programs easier to write, understand and maintain.
This topic is in both Paper 1 and Paper 2.
Big O Notation
O(n)
Big O Notation is a way of describing how the time complexity (how long an algorithm takes) and space complexity (how much memory it uses) grows as the size of the input increases. This allows algorithms to be compared in terms of efficiency, using the letter n to refer to the size of the input.
Complexity types:
-
Constant - O(1) - The algorithm’s time or space stays the same no matter how large the input is.
-
Linear - O(n) - The time or memory grows directly in proportion to the size of the input.
-
Polynomial - O(n²) - The growth increases in proportion to the square of the input, often seen in algorithms with nested loops.
-
Exponential - O(2ⁿ) - The time or memory doubles with each additional input element, becoming extremely slow very quickly.
-
Logarithmic - O(log n) - The algorithm’s time grows very slowly as the input size increases, often achieved by repeatedly halving the data.
-
Linearithmic - O(n log n) - A combination of linear and logarithmic behaviour, common in efficient sorting algorithms like merge sort.
Algorithm Complexity
Best-case, average-case and worst-case complexity describe how an algorithm performs under different input conditions.
-
Best-case complexity is the time or space required when the algorithm meets the most favourable input, allowing it to finish as quickly or efficiently as possible.
-
Average-case complexity represents the expected performance across typical or random inputs, giving a realistic view of how the algorithm behaves in normal use.
-
Worst-case complexity is the maximum time or space the algorithm could ever require, used to guarantee performance even in the least favourable situation.
Sorting and searching algorithms often have different case complexities for time and space.
Questo's Key Terms
Pseudocode
Procedural Language: input, output, comments, variables, casting, count-controlled iteration, condition-controlled iteration, logical operators, selection, string handling, subroutines, arrays, files
Big O Notation: time complexity, space complexity, constant, linear, polynomial, exponential, logarithmic, linearithmic, best-case, average-case, worst-case
Did You Know?
Minecraft doesn’t load the entire world at once; instead, it divides the world into chunks and only generates or loads the chunks near the player. Finding, saving and retrieving these chunks uses data structures like trees and hash maps, which allow the game to look up a chunk in about O(log n) or even O(1) time, minimising lag even in large worlds.
