ReviseRush logoREVISERUSH

AQA GCSE Computer Science

Algorithms: searching, sorting and efficiency — AQA GCSE Computer Science revision

Free revision notes, key terms, common exam traps and 5 practice questions with answers. About 7 minutes to read.

Computational thinking

  • Abstraction means removing unnecessary detail from a problem so you can focus on what matters, e.g. a map ignoring building heights to show routes.
  • Decomposition means breaking a large problem down into smaller, more manageable sub-problems that are easier to solve and test.
  • Algorithmic thinking is working out the logical steps needed to solve a problem, often shown as a sequence of instructions.
  • Algorithms can be represented as flowcharts (diagrams with shapes for start/end, process, decision and input/output) or as pseudocode (structured, language-independent code-like text).

Searching algorithms

  • Linear search checks each item in a list one by one from the start until the target is found or the list ends; it works on unsorted or sorted lists.
  • Linear search has worst-case time complexity O(n) — checking every item if the target is last or missing.
  • Binary search repeatedly checks the middle item of a sorted list, discarding the half that cannot contain the target, until the target is found.
  • Binary search requires the list to be sorted first and has time complexity O(log n), making it much faster than linear search for large lists.

Key terms

Abstraction
Removing unnecessary detail to focus on the important features of a problem.
Decomposition
Breaking a large problem into smaller, manageable sub-problems.
Algorithm
A precise sequence of steps to solve a problem or complete a task.
Linear search
Checking each item in a list in turn until the target is found or the list ends.
Binary search
Repeatedly halving a sorted list to quickly locate a target item.
Bubble sort
Sorting by repeatedly swapping adjacent out-of-order items.

Common exam traps

  • Trying to use binary search on an unsorted list — it only works on sorted data.
  • Confusing O(n) with O(n²) — O(n²) grows far more steeply as data size increases.
  • Thinking bubble sort is efficient for large lists — it is simple but slow, O(n²).

Practice questions with answers

  1. 1. Which searching algorithm requires the list to be sorted?

    • • Linear search
    • • Binary search
    • • Bubble sort
    • • Insertion sort

    Answer: Binary search

    Binary search relies on halving a sorted list, so the list must already be sorted.

  2. 2. What is the time complexity of linear search in the worst case?

    Answer: O(n)

    Linear search may need to check every item, giving O(n) worst-case complexity.

  3. 3. What does abstraction mean in computational thinking?

    • • Breaking a problem into smaller parts
    • • Removing unnecessary detail to focus on key features
    • • Writing code in a specific language
    • • Testing a program with random data

    Answer: Removing unnecessary detail to focus on key features

    Abstraction simplifies a problem by hiding irrelevant detail.

  4. 4. Name the process of breaking a large problem into smaller sub-problems.

    Answer: Decomposition

    Decomposition splits complex problems into manageable pieces.

  5. 5. In bubble sort, what happens to adjacent items that are out of order?

    • • They are deleted
    • • They are swapped
    • • They are ignored
    • • They are merged

    Answer: They are swapped

    Bubble sort swaps adjacent items if they are in the wrong order.

Keep going in the app

This topic has 55 questions in total, plus flashcards, cram mode and Grade 9 Push challenges.

Open the full topic Quick-fire quiz

More free Computer Science revision

ReviseRush is an independent educational revision aid. It is not affiliated with, endorsed by or connected to AQA, Edexcel, OCR, WJEC, Pearson or any exam board. All notes and questions are original. Always check content against your official course and specification. No grade outcome is guaranteed.