AQA 7517 4.4.4.3: Order of complexity
The free BugBot lessons that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
The last lesson counted operations as a function of n. Big O notation is the shorthand for that function's growth. It throws away the detail that stops mattering when n is large, and keeps the one thing that does: the shape of the curve.
- Keep the dominant term, drop the constants
- The orders you need
- Deriving the complexity of code
- Exponential growth in code
- Best, average and worst case
- Space complexity
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A5.2 Big O notation Algorithms and complexity
Dominant terms, the orders of complexity from O(1) to O(2^n), deriving complexity from code, best, average and worst case, and space… - A5.9 Project: plan the route, then drive it Algorithms and complexity
Choose and justify a route planner, build the mat's graph, find the shortest route with Dijkstra's algorithm and drive it. - A15.7 Calculation and theory questions Exam preparation
Number representation, floating point, Boolean logic, state machines and complexity answered quickly and checked.
Try it on a robot
The task from A5.2 Big O notation, 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.3 and is not endorsed by the board.