Maths and computer science · Solid · Dissertation or artefact

Which sorting algorithm is fastest?: a maths EPQ idea

Why it works as an EPQ

You can prove complexity results and then test them by timing your own code, so theory meets evidence.

Scope and difficulty

Solid. Solid. Three or four algorithms, lists of several sizes and shapes.

The maths

Builds on these A Level topics: Sequences and series · Exponentials and logarithms · Proof.

You would learn:

• Big O notation
• Recurrences such as T(n) = 2T(n/2) + n
• Best, worst and average cases

Learning maths beyond the course is expected in a maths EPQ, but you must understand and explain everything you use.

One possible plan

1. Analyse each algorithm's comparisons in the best, worst and average case.
2. Solve the merge sort recurrence.
3. Time your own implementations on random, sorted and nearly sorted lists.
4. Judge when Big O predicts real performance and when it does not.

Pitfalls

• Timing code without repeats or with other programs running.
• Using library sort functions you have not analysed.

Where to start reading

• Introduction to Algorithms (Cormen, Leiserson, Rivest and Stein), sorting chapters
• Search for: master theorem recurrences

Prefer books, lecture notes, journal articles and official data to a single website, and record every source as you read (how to reference).

Making something? Read the artefact guide first: an artefact still needs a research-based written report.

Similar ideas

• How search engines rank pagesHow can matrices and probability rank web pages, and how could the ranking be manipulated?Computer scienceAmbitiousDissertation
• How QR codes survive damageHow can a damaged QR code still be read? The mathematics of error-correcting codesComputer scienceSolidDissertation or artefact
• How compression makes files smallerHow can a file be made smaller without losing anything, and what is the limit?Computer scienceSolidDissertation or artefact
• How a neural network learnsHow does a neural network learn, and how much of it is calculus you already know?Computer scienceAmbitiousDissertation or artefact

All maths and computer science ideas · all 93 ideas

Your EPQ must be your own work. These pages coach: ideas, structure, checklists and planning. Submitting text, proofs, code or analysis written by someone else or by an AI tool as your own is malpractice. How to use help and AI honestly.