Algorithms — OCR A-Level Study Guide

Overview

Welcome to the study of Algorithms, a cornerstone of OCR's A-Level Computer Science (H446) and a fundamental part of computational thinking. This topic, specification reference 2.1, is not just about memorising steps; it's about understanding the logic, efficiency, and trade-offs involved in solving problems programmatically. In your Component 02 exam, you will be expected to analyse, design, and evaluate algorithms, often using the official OCR Pseudocode. Questions will test your ability to trace algorithm execution, compare their performance characteristics using Big O notation, and apply them to practical scenarios. A solid grasp of this topic is crucial as it links directly to data structures and forms the basis for more advanced problem-solving, making it a frequent and high-value area for assessment.

Key Concepts

Concept 1: Algorithm Efficiency and Big O Notation

Algorithm efficiency is a measure of how many resources (primarily time and memory) an algorithm consumes in relation to the size of its input (n). We use Big O notation to provide an upper bound on this, describing the worst-case scenario. This allows us to compare algorithms in a standardised way, ignoring machine speed and focusing on computational complexity. For the exam, you must be able to identify and compare the following complexities.

• O(1) - Constant Time: The algorithm takes the same number of steps regardless of input size. A classic example is accessing an element in an array using its index.
• O(log n) - Logarithmic Time: The algorithm's time complexity grows logarithmically with the input size. With each step, the problem size is reduced by a constant factor (usually halved). Binary Search