AQA 7517 4.4.4.2: Maths for understanding Big-0 notation
The free BugBot lesson that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
At GCSE (F5.9) you compared bubble sort and merge sort by counting their comparisons on one list. At A level you compare algorithms in general: not "how long did it take on this list" but "how does the work grow as the problem gets bigger". This lesson sets up the ideas and the maths; the next one turns them into Big O notation.
- Why not use a stopwatch?
- Time and space
- The maths: four kinds of function
- Permutations
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A5.1 Comparing algorithms Algorithms and complexity
Time and space efficiency as functions of the size of the problem; linear, polynomial, exponential and logarithmic functions; permutations…
Try it on a robot
The task from A5.1 Comparing algorithms, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.4.4.2 and is not endorsed by the board.