CS2: Efficiency of Algorithms
Understanding how efficient algorithms are and why some algorithms are better than others for solving the same problem.
📋 What is Algorithm Efficiency?
Definition: Algorithm efficiency measures how much time and/or memory an algorithm uses to solve a problem. A more efficient algorithm uses fewer resources (time and space) to produce the same result.
Two algorithms might solve the same problem, but one could be much faster or use less memory. Understanding efficiency helps you choose the best algorithm for a given situation.
Key Concept - Time Complexity:
Time complexity describes how the running time of an algorithm grows as the size of the input increases. It is not measured in seconds - it is measured in terms of the number of operations relative to input size (n).
Time complexity describes how the running time of an algorithm grows as the size of the input increases. It is not measured in seconds - it is measured in terms of the number of operations relative to input size (n).
📊 Comparing Algorithms
Key Principle: When two algorithms solve the same problem, the more efficient one will complete in fewer steps, especially as the input size increases.
Example: Finding a Name in a Phone Book
Algorithm A (Linear approach): Read every name from the first page until you find the one you want.
Algorithm B (Binary approach): Open the book in the middle. If the name is earlier, discard the second half. Repeat with the remaining half.
For a phone book with 1000 names:
- Algorithm A: Up to 1000 checks (worst case)
- Algorithm B: At most 10 checks (worst case)
Algorithm B is far more efficient for large phone books!
| Input Size (n) | Linear - O(n) | Binary - O(log n) | Difference |
|---|---|---|---|
| 10 | 10 checks | 4 checks | 2.5x faster |
| 100 | 100 checks | 7 checks | 14x faster |
| 1,000 | 1,000 checks | 10 checks | 100x faster |
| 1,000,000 | 1,000,000 checks | 20 checks | 50,000x faster |
📈 How Efficiency Varies with Input Size
Crucial Point: Some algorithms that seem fast for small inputs become extremely slow for large inputs. The rate at which time increases matters more than the time for a single small input.
Common Time Complexities (Big O Notation)
| Complexity | Name | Meaning | Example |
|---|---|---|---|
| O(1) | Constant time | Time stays the same regardless of input size | Accessing an array element by index |
| O(log n) | Logarithmic | Time increases very slowly - halves the problem each step | Binary search |
| O(n) | Linear | Time increases proportionally with input size | Linear search |
| O(n log n) | Linearithmic | Time increases slightly more than linearly | Merge sort |
| O(n²) | Quadratic | Time increases with the square of input size | Bubble sort |
Order of Efficiency (Best to Worst):
O(1) > O(log n) > O(n) > O(n log n) > O(n²)
As n gets larger, the difference between these becomes dramatic.
O(n²) algorithms become unusable for large datasets.
O(1) > O(log n) > O(n) > O(n log n) > O(n²)
As n gets larger, the difference between these becomes dramatic.
O(n²) algorithms become unusable for large datasets.
🔢 Practical Implications
Scenario: Sorting Student Records
A school has 10,000 student records to sort by surname.
Bubble sort (O(n²)): Up to 100,000,000 comparisons
Merge sort (O(n log n)): Approximately 140,000 comparisons
Merge sort is over 700 times faster for this dataset!
When Does Efficiency Matter?
- Small datasets (n < 100): The difference between algorithms is small - simpler algorithms may be acceptable
- Medium datasets (100-10,000): Choice of algorithm starts to matter - O(n²) begins to slow down
- Large datasets (10,000+): Algorithm choice is critical - O(n²) algorithms may take hours or days
Exam Focus: At GCSE level, you need to understand that some algorithms are more efficient than others and explain WHY. You should be able to compare linear search vs binary search, and bubble sort vs merge sort, in terms of efficiency.
🔬 Measuring Efficiency Practically
Counting Operations
One way to measure efficiency is to count the number of key operations an algorithm performs.
Counting Comparisons in Linear Search
FOR i ← 0 TO LENGTH(list) - 1
IF list[i] = target THEN // This comparison happens n times
OUTPUT "Found at position ", i
ENDIF
NEXT i
Comparisons: n (where n is the length of the list)
Best case: 1 comparison (item is first)
Worst case: n comparisons (item is last or not present)
Counting Comparisons in Binary Search
Each step halves the remaining search space.
After 1 comparison: n/2 items remain
After 2 comparisons: n/4 items remain
After k comparisons: n/2^k items remain
Maximum comparisons: log₂(n)
For 1,000,000 items: only 20 comparisons needed!
⚖️ Time vs Space Efficiency
| Aspect | Time Efficiency | Space Efficiency |
|---|---|---|
| Measures | How fast the algorithm runs | How much memory it uses |
| Trade-off | Using more memory can speed things up | Using less memory may slow things down |
| Example | Merge sort is fast but needs extra arrays | Bubble sort is slow but uses no extra memory |
| GCSE focus | Time complexity is the main focus | Awareness that memory matters too |
Trade-off Principle:
Sometimes you can make an algorithm faster by using more memory (e.g. storing pre-computed results). Other times, using less memory means recalculating values and running slower. This is the time-space trade-off.
Sometimes you can make an algorithm faster by using more memory (e.g. storing pre-computed results). Other times, using less memory means recalculating values and running slower. This is the time-space trade-off.
❓ Practice Questions
Q1: What does time complexity measure?
Q2: An algorithm has O(n) time complexity. If it takes 5 seconds to process 1000 items, approximately how long would it take to process 5000 items?
Q3: Explain why binary search is more efficient than linear search for large datasets.
Q4: Give an example of a situation where using a less efficient algorithm might be acceptable.
Q5: A bubble sort on 100 items takes up to 10,000 comparisons. How many comparisons would it take for 1000 items?
✅ Answers
- Time complexity measures how the running time of an algorithm grows as the input size increases. It describes the relationship between input size and number of operations.
- Approximately 25 seconds. O(n) means time is proportional to input size. 5000 is 5 times 1000, so 5 × 5 = 25 seconds.
- Binary search halves the search space each step, so it needs at most log₂(n) comparisons. Linear search checks every item, needing up to n comparisons. For large n, log₂(n) is vastly smaller than n.
- When the dataset is very small (e.g. sorting 10 items), the difference between efficient and inefficient algorithms is negligible. Also, when the algorithm only runs once and speed is not critical.
- Up to 1,000,000 comparisons. Bubble sort is O(n²), so for 1000 items: 1000 × 1000 = 1,000,000.
🎯 Exam Tips
- You don't need to calculate exact Big O values - just understand the concept
- Be able to explain that binary search is more efficient than linear search because it halves the search space
- Be able to explain that merge sort is more efficient than bubble sort for large datasets
- Use the terms "time complexity" and "proportional to" in your answers
- If asked to compare algorithms, always mention how performance changes as input size grows
- Remember: O(n²) algorithms become impractical for large datasets
⚠️ Common Errors
✗ Thinking a faster algorithm is always better regardless of memory usage ✓ Efficiency considers both time and space; a faster algorithm may use significantly more memory, which could be unsuitable for constrained systems.
✗ Confusing time complexity with actual running time ✓ Time complexity describes how the number of operations grows with input size (Big O), not the actual clock time a program takes to run.
✗ Believing O(n) is always worse than O(log n) for all inputs ✓ O(log n) scales better for large inputs, but for very small datasets the constant overhead of O(log n) algorithms may make O(n) faster in practice.
✗ Thinking Big O notation measures exact step counts ✓ Big O notation describes the upper bound of growth rate as input tends to infinity, ignoring constants and lower-order terms.
✍️ Model Answer
Full-Mark Response
Two algorithms solve the same problem. Algorithm A has time complexity O(n²) and Algorithm B has O(n log n). Explain which algorithm is more efficient for large datasets and why. [4 marks]
Algorithm B (O(n log n)) is more efficient for large datasets. As n increases, n² grows much faster than n log n. For example, with n = 1000: Algorithm A performs roughly 1,000,000 operations while Algorithm B performs roughly 10,000 operations. Big O notation shows that Algorithm B scales better because its growth rate is lower, meaning it will be significantly faster for large inputs. However, for very small datasets Algorithm A might be comparable due to lower constant overhead.
📊 AO Deep Dive
Assessment Objective Analysis
AO1 (Computational Thinking — 40%): Demonstrate knowledge and understanding of the principles and concepts of computer science, including algorithm efficiency and Big O notation for AQA 8525, OCR J277 & Edexcel 1CP2.
AO2 (Application — 40%): Apply knowledge and understanding of computer science, including algorithm efficiency and Big O notation to analyse problems in computational terms and to design, write and evaluate solutions.
AO3 (Evaluation — 20%): Evaluate the effectiveness, correctness and efficiency of computational solutions, including algorithm efficiency and Big O notation, and make reasoned judgements about trade-offs.
📝 Exam Technique
GCSE Computer Science Exam Tips:
When comparing algorithm efficiency, always refer to Big O notation and explain how the number of operations grows with input size. Use concrete examples (e.g. n=100, n=1000) to illustrate differences. Remember that time complexity is about growth rate, not actual speed. Mention that Big O ignores constants and lower-order terms. If asked to compare algorithms, consider both time AND space complexity where relevant.
When comparing algorithm efficiency, always refer to Big O notation and explain how the number of operations grows with input size. Use concrete examples (e.g. n=100, n=1000) to illustrate differences. Remember that time complexity is about growth rate, not actual speed. Mention that Big O ignores constants and lower-order terms. If asked to compare algorithms, consider both time AND space complexity where relevant.
📝 Exam Questions by Topic
🎬 Video Resources
Ready to ace your GCSE Computer Science exams?
Get the best revision books and guides to boost your grades.