Correctness, Efficiency and Complexity
Arguing that an algorithm terminates and produces the required result, while comparing execution time and space requirements as input grows.
How to study A-level Computer Science
Define the problem and representation, trace the state change, justify the algorithm or architecture, then test the result against requirements, evidence and constraints.
Core concepts
Concept 1
Correctness depends on the specification, valid preconditions, maintained invariants and the required postcondition.
Exam cue: State the input size and dominant repeated operation before giving a complexity.
Concept 2
Time and space complexity describe resource growth rather than the exact running time on one machine.
Exam cue: Separate worst, average and best cases when the distinction changes the comparison.
Concept 3
Algorithms solving the same task can be compared by growth rate, data characteristics and implementation trade-offs.
Exam cue: Use logical reasoning and tests together: tests provide evidence but do not prove all cases.
Risk pitfalls and guardrails
Equating a fast result on one small input with a better complexity class.
Guardrail: Do not substitute a memorised definition or generic advantage until you have identified the input, state, stakeholder and constraint in the task.
Ignoring auxiliary memory when comparing space requirements.
Guardrail: Do not substitute a memorised definition or generic advantage until you have identified the input, state, stakeholder and constraint in the task.
Claiming exhaustive correctness from a few successful tests.
Guardrail: Do not substitute a memorised definition or generic advantage until you have identified the input, state, stakeholder and constraint in the task.
Memory anchors
Precondition
A precondition must hold before an algorithm is expected to work correctly.
Postcondition
A postcondition describes what must be true after successful completion.
Invariant
An invariant remains true through each relevant step or iteration.
Time Complexity
Time complexity describes how the work grows with input size.
Space Complexity
Space complexity describes how required storage grows with input size.
Checkpoint rule
Do the check-up only after you can summarize each concept in one sentence and identify one dangerous pitfall from memory.
Knowledge Check (after reading)
Short check-up to confirm understanding of this module.
Check-up Questions
What does O(n²) describe?
An algorithm performs 5n + 20 primitive operations. What is its asymptotic time complexity?
Answer all questions to submit.
Next step personalized recommendations
Continue learning
Move forward only after this module is stable.
What is Pass Harbor?
Completely free exam prep for 247 UK exams.
- Practice questions
- Flashcards
- Study guides
- Mock exams
- No registration
- No paywall
- Start instantly
“No more expensive exam prep. Quality study tools should be accessible to everyone.”