- Define and explain Measuring Efficiency in your own words
- Use key terms such as Big-O notation accurately
- Apply what you have learned to new examples and questions
- Avoid the common mistakes learners make with this topic
This lesson focuses on Measuring Efficiency: compare algorithms using Big-O notation and worst cases.
Compare algorithms using Big-O notation and worst cases.
Key ideas
Bubble sort is simple, not fast
Bubble sort is easy to understand and to code, which is why it is taught first — but comparing every pair of neighbours makes it slow, at O(n²) in the worst case. Python's built-in sort uses a far cleverer algorithm called Timsort. In exams, know bubble sort's steps and its weakness.
Worst case is what matters
An algorithm might get lucky and find the target first try, but engineers plan for the worst case — the slowest possible run. Big-O describes this growth: O(n) means doubling the input roughly doubles the time, while O(n²) means doubling the input roughly quadruples it.
Key term — Big-O notation: A way of describing how an algorithm's running time grows as the input grows — for example, linear search is O(n) and binary search is O(log n).
How many comparisons does linear search need in the worst case to find an item in a list of 50?
50 — every item must be checked if the target is last or missing.
Answer: 50 — every item must be checked if the target is last or missing.
- Claiming bubble sort is efficient because it is short to write Correction: short code is not fast code — bubble sort's nested comparisons make it O(n²), slow for large lists.
- Using binary search on an unsorted list Correction: sort the list first, or use linear search — binary search on unsorted data gives wrong answers, not just slow ones.
Practice
About 20 — each step halves the remaining items, so a million shrinks to one in roughly 20 halvings.
O(n²) — quadrupling when the input doubles is the signature of quadratic growth.
False — it needs sorted data, and for tiny or unsorted lists the overhead is not worth it; the best algorithm depends on the situation.
[3, 5, 1, 8] — 5 and 3 swap, 5 and 8 stay, 8 and 1 swap.
Quick check
Which of these best defines "Big-O notation"?
Why might linear search beat binary search for a single search?
- Measuring Efficiency: compare algorithms using Big-O notation and worst cases.
- Bubble sort is simple, not fast: Bubble sort is easy to understand and to code, which is why it is taught first — but comparing every pair of neighbours makes it slow, at O(n²) in the worst case.
- binary search: Repeatedly halving a sorted list to find a target — comparing with the middle item and discarding the half that cannot contain it.
- Watch out for: claiming bubble sort is efficient because it is short to write