Algorithms

Algorithms are the core of computer science: well-defined, finite procedures that transform inputs into outputs. This section covers the design, analysis, and implementation of the algorithms you must understand for A-Level, including their time and space complexity.

• Linear search — $O(n)$ sequential scan; when to use it (unsorted data, small datasets)
• Binary search — $O(\log n)$ on sorted data; the divide-and-conquer paradigm
• Trace tables — stepping through algorithm execution to verify correctness

• Bubble sort, insertion sort, merge sort, quick sort — their mechanisms, complexity, and stability
• Best-case, average-case, and worst-case analysis using Big-O notation
• Comparison of sorting algorithms — when each is appropriate

• Depth-first search (DFS) and breadth-first search (BFS) — traversal strategies
• Dijkstra”s shortest path — weighted graph optimisation
• Representations — adjacency matrix vs. adjacency list trade-offs

• Big-O, Big-$\Omega$, and Big-$\Theta$ notation — formal definitions and practical use
• Time vs. space complexity — analysing both dimensions
• Classifying common algorithms — constant, logarithmic, linear, linearithmic, quadratic, exponential

1. Trace algorithms by hand on small inputs before writing code. This builds the intuition needed for exam trace-table questions.
2. Learn the complexity classes cold: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$. You should be able to classify any A-Level algorithm instantly.
3. Understand why merge sort is $O(n \log n)$ and bubble sort is $O(n^2)$, not just that it is. Exam questions test reasoning, not memorisation.
4. Compare algorithms in terms of time, space, and stability. Comparison questions appear frequently.
5. Practice deriving Big-O from code or pseudocode, counting operations line by line.

Work through the pages in sidebar order. Each page contains definitions, step-by-step traces, worked exam examples, and practice problems. Start with searching and sorting, then move to graph algorithms and complexity analysis.

Throughout this section we use the following notation:

This section provides comprehensive A-Level Computer Science content for Algorithms, covering all specification points with detailed explanations, worked examples, and practice questions.

Each page in this section includes:

• Definitions: Clear, precise explanations of key concepts
• Worked Examples: Step-by-step solutions with annotations
• Practice Questions: Multiple-choice and structured questions with mark schemes
• Common Pitfalls: Errors to avoid and how to fix them
• Exam Tips: Strategies for maximising marks in this topic

1. Read the introductory page to understand the topic overview
2. Work through each sub-topic in order
3. Attempt the practice questions before checking solutions
4. Use the flashcards to revise key terminology
5. Complete the diagnostic test to identify remaining gaps

• Core definitions and principles
• Application to examination-style questions
• Links to related topics across the specification
• Assessment objective alignment (AO1, AO2, AO3)

• Active Recall: Test yourself regularly rather than re-reading notes
• Spaced Practice: Revisit this topic at increasing intervals
• Interleaving: Mix with other topics during revision sessions
• Elaboration: Explain concepts in your own words

Focus on command word interpretation and mark scheme analysis. Practice timing yourself on questions to build speed and accuracy. Review examiner reports for this topic to understand common student errors.

This landing page provides comprehensive coverage of Computer Science content for the Alevel qualification, with detailed explanations, worked examples, and practice questions aligned to the specification.

This page includes:

• Key Definitions: Precise explanations of essential concepts
• Core Concepts: Detailed treatment of fundamental principles
• Worked Examples: Step-by-step solutions demonstrating application
• Practice Questions: Examination-style questions with mark schemes
• Common Pitfalls: Frequent errors and how to avoid them
• Exam Tips: Strategies for maximising marks

1. Read through the introductory material to establish context
2. Study the definitions and core concepts carefully
3. Work through the worked examples, following each step
4. Attempt the practice questions independently
5. Review your answers against the provided solutions
6. Note any areas requiring further revision

• Foundational definitions and terminology
• Application of principles to examination contexts
• Connections to related topics within the specification
• Assessment objective alignment

• Active Recall: Test yourself on the material rather than passively re-reading
• Spaced Repetition: Review this content at increasing intervals
• Interleaving: Mix this topic with others during study sessions
• Elaborative Interrogation: Ask yourself why each concept works

Practise applying these concepts under timed conditions. Focus on understanding what each question is asking and how marks are allocated. Review examiner reports to learn from common mistakes made by other students.

1. Confusing Big O with Big Θ. Big O is an upper bound (the worst case is AT MOST this). Big Θ is a tight bound (the worst case is EXACTLY this). Saying “bubble sort is O(n)” is technically true but misleading — it should be Θ(n²). Always use the tightest bound you can prove.

2. Assuming all sorting algorithms are O(n log n). Merge sort and quicksort (average case) are O(n log n), but bubble sort and insertion sort are O(n²). Quick sort’s worst case is O(n²) on already sorted input. Always specify best, average, and worst case.

3. Forgetting that graph algorithms depend on representation. BFS and DFS on an adjacency matrix are O(V²); on an adjacency list they are O(V + E). The choice of data structure affects complexity — always state your representation.

4. Confusing time complexity with space complexity. An algorithm can be fast but use a lot of memory (e.g., merge sort uses O(n) extra space). Or it can be slow but use little memory (e.g., in-place quicksort uses O(log n) stack space). Both matter.

5. Not understanding that lower bounds exist. Comparison-based sorting has a lower bound of Ω(n log n) — no comparison sort can do better in the worst case. This is proven by the decision tree argument. Non-comparison sorts (counting sort, radix sort) can beat this but only for specific input types.

Algorithms are, at their heart, recipes for solving problems. Just as a recipe tells you the exact steps to bake a cake — which ingredients to mix, in what order, and for how long — an algorithm specifies a precise sequence of steps that transform an input into a desired output. The study of algorithms is about finding the most efficient recipes: ones that use the fewest steps, the least memory, or the least time. Not all algorithms for the same problem are equal — sorting a list can be done in O(n^2) time with simple approaches or O(n log n) with more clever ones, and the difference matters enormously when n is large.

The framework for comparing algorithms is called complexity analysis. Big O notation captures how an algorithm’s running time or memory usage grows as the input size increases. The intuition is straightforward: if you double the input size and the running time quadruples, you are looking at O(n^2) behaviour. If doubling the input only adds a constant amount of extra time, you have O(log n) — incredibly efficient. This abstraction lets you compare algorithms without worrying about hardware details or implementation specifics; you are measuring the growth rate, which is an intrinsic property of the algorithm itself.

Different problem types call for different algorithmic strategies. Divide and conquer splits a problem into smaller subproblems, solves them recursively, and combines the results — merge sort and binary search are classic examples. Greedy algorithms make the locally optimal choice at each step, hoping to reach a global optimum — they work well for problems like finding minimum spanning trees. Dynamic programming breaks problems into overlapping subproblems and stores their solutions to avoid redundant work. Understanding which strategy fits a given problem is the essence of algorithm design, and it is a skill that applies far beyond examinations — it is the foundation of efficient software.

• Computer Science
• Searching Algorithms
• Sorting Algorithms