Fundamentals of algorithms — AQA A-Level Computer Science

Fundamentals of algorithms is the bedrock of computer science, covering the design, analysis, and implementation of step-by-step procedures for solving problems. This topic introduces you to the core concepts of computational thinking—decomposition, pattern recognition, abstraction, and algorithmic thinking—which are essential for breaking down complex problems into manageable steps. You'll learn how to represent algorithms using pseudocode and flowcharts, and how to evaluate their efficiency in terms of time and space complexity using Big O notation. Mastery of this topic is crucial because algorithms underpin everything from simple sorting tasks to complex artificial intelligence systems, and it forms the foundation for more advanced topics like data structures and optimisation.

In the AQA A-Level specification, this topic is assessed through both written exams and non-exam assessment (NEA). You'll need to be able to trace algorithms, identify errors, and write your own solutions to problems. Key algorithms you must know include linear and binary search, bubble sort, merge sort, insertion sort, and quicksort. You'll also explore the trade-offs between different algorithms—for example, why merge sort is more efficient than bubble sort for large datasets, but requires more memory. Understanding these trade-offs is vital for making informed decisions when designing software in real-world scenarios.

Beyond exams, algorithmic thinking is a transferable skill that enhances your problem-solving abilities in any field. This topic connects directly to data structures (e.g., how arrays and lists affect search and sort efficiency), programming (implementing algorithms in code), and computational mathematics (e.g., recursion and divide-and-conquer strategies). By the end of this topic, you should be able to analyse an algorithm's efficiency, compare algorithms for the same task, and justify your choice based on context—skills that are highly valued in university and industry.

• →Computational thinking: Decomposition (breaking a problem into sub-problems), pattern recognition (identifying similarities), abstraction (focusing on essential details), and algorithmic thinking (designing step-by-step solutions).
• →Algorithm efficiency: Big O notation (e.g., O(1), O(n), O(n^2), O(log n)) to describe worst-case time complexity, and understanding space complexity (memory usage).
• →Search algorithms: Linear search (O(n)) and binary search (O(log n))—know when each is appropriate (binary search requires sorted data).
• →Sorting algorithms: Bubble sort (O(n^2)), insertion sort (O(n^2)), merge sort (O(n log n)), and quicksort (average O(n log n), worst O(n^2)). Understand how each works and their stability.
• →Algorithm representation: Using pseudocode (AQA standard) and flowcharts to design and communicate algorithms clearly.

• Award credit for correctly identifying the precondition for binary search (data must be sorted)
• Demonstrate the ability to trace a binary search algorithm on a given dataset, highlighting low, high, and mid indices
• Explain why linear search has O(n) complexity and binary search has O(log n) complexity
• Implement search algorithms in a programming language with appropriate syntax

• 💡When writing pseudocode for binary search, clearly define the low and high pointers and the loop condition
• 💡In written exams, always state the precondition for binary search (sorted list) before describing the algorithm
• 💡Use Big O notation precisely for comparisons: O(n) vs O(log n), and mention space complexity if relevant
• 💡Practice tracing algorithms on paper to avoid off-by-one errors in mid calculations
• 💡When tracing algorithms, always use a trace table with columns for each variable and output. This helps you systematically track changes and avoid missing steps. In exams, trace tables are often provided—fill them in carefully.
• 💡For algorithm design questions, start by writing clear pseudocode that follows AQA conventions (e.g., indentation, keywords like IF, THEN, ELSE, WHILE, FOR). Use meaningful variable names and include comments to explain your logic. This makes it easier for examiners to award partial credit.
• 💡When comparing algorithms, always mention both time and space complexity. For example, 'Merge sort has O(n log n) time complexity but requires O(n) additional space, whereas quicksort is in-place (O(log n) space) but has a worst-case O(n^2) time.' This shows depth of understanding.

• Confusing the index of the middle element when calculating mid point in binary search, especially with integer division
• Assuming binary search works on unsorted data
• Misunderstanding the efficiency difference, e.g., believing binary search is always faster regardless of data size
• Forgetting to handle the case when the target element is not found
• Misconception: Binary search can be used on any list. Correction: Binary search only works on sorted lists. If the list is unsorted, you must either sort it first (which adds overhead) or use linear search.
• Misconception: Big O notation describes the exact runtime. Correction: Big O describes the growth rate of runtime as input size increases, not the actual time. An O(n^2) algorithm may be faster than an O(n log n) one for small n due to constant factors.
• Misconception: Merge sort is always better than quicksort. Correction: While merge sort has guaranteed O(n log n) time, quicksort is often faster in practice due to lower constant factors and better cache performance, though it has a worst-case O(n^2) if pivot selection is poor.