You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
When solving a problem, there are often many possible algorithms. But how do you decide which one is best? Algorithm efficiency is the study of how much time and space (memory) an algorithm requires as the size of the input grows.
Consider searching for a name in a phone book with 1,000,000 entries:
Both solve the same problem, but binary search is vastly more efficient. For real-world applications processing millions of records, choosing the right algorithm can mean the difference between a result appearing in milliseconds or taking hours.
We measure the efficiency of an algorithm by counting the number of basic operations (comparisons, swaps, assignments, etc.) it performs relative to the input size, n.
We focus on how the number of operations grows as n increases, rather than the exact count.
| Big O Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing an array element by index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort |
| O(n²) | Quadratic | Bubble sort, insertion sort (worst case) |
| O(2ⁿ) | Exponential | Some brute-force algorithms |
Big O notation describes the worst-case performance of an algorithm. It tells you the upper bound on the number of operations as the input size grows.
Key rules:
Why ignore constants and lower terms? Because as n becomes very large, the dominant term overwhelms everything else. If n = 1,000,000:
Adding 1,000,000 to 1,000,000,000,000 makes virtually no difference.
The hierarchy of complexity classes — from fastest (top) to slowest (bottom) — looks like this:
graph TD
A["Time complexities ranked"] --> B["O(1) constant — array index"]
B --> C["O(log n) logarithmic — binary search"]
C --> D["O(n) linear — linear search"]
D --> E["O(n log n) linearithmic — merge sort"]
E --> F["O(n^2) quadratic — bubble sort"]
F --> G["O(2^n) exponential — brute force"]
Here is how different time complexities compare for various input sizes:
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 33 | 100 |
| 100 | 1 | 7 | 100 | 664 | 10,000 |
| 1,000 | 1 | 10 | 1,000 | 9,966 | 1,000,000 |
| 1,000,000 | 1 | 20 | 1,000,000 | 19,931,569 | 1,000,000,000,000 |
You can see that O(n²) algorithms become impractical very quickly as n grows.
As well as time, we can measure space complexity — how much extra memory an algorithm needs.
| Algorithm | Space Complexity | Explanation |
|---|---|---|
| Linear search | O(1) | Only needs a few variables |
| Binary search | O(1) | Only needs pointers (iterative version) |
| Bubble sort | O(1) | Sorts in place |
| Insertion sort | O(1) | Sorts in place |
| Merge sort | O(n) | Needs extra arrays for merging |
Exam Tip: At GCSE level, you are mainly expected to understand time complexity and be able to identify whether an algorithm is O(1), O(n), O(n²), or O(log n). You should be able to explain what these mean and compare the efficiency of different algorithms.
Most algorithms perform differently depending on the input:
| Case | Meaning | Example (Linear Search) |
|---|---|---|
| Best case | Fewest operations possible | Target is the first element — O(1) |
| Worst case | Most operations possible | Target is last or not present — O(n) |
| Average case | Expected operations on random input | About n/2 comparisons — O(n) |
Big O typically refers to the worst case, which gives an upper bound guarantee.
For your GCSE exam, you should be able to:
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) | O(1) |
| Binary search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
Read each fragment and determine its time complexity in terms of n.
Fragment 1:
x = list[0]
OUTPUT x
A fixed number of operations regardless of list size → O(1).
Fragment 2:
FOR i = 0 TO n - 1
OUTPUT list[i]
NEXT i
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.