Efficiency of Simple Algorithms (AQA GCSE Computer Science): Revision Notes
Efficiency of simple algorithms
Understanding algorithm efficiency
When we write computer programmes, there's often more than one way to solve the same problem. This is an important concept in computer science - just because an algorithm works doesn't mean it's the best way to do it!
Algorithm efficiency refers to how well an algorithm performs, specifically how much time and resources it takes to complete its task. Since computers run at different speeds, we don't measure efficiency by actual time taken. Instead, we count the number of steps or operations an algorithm needs to complete.
Think of it like comparing two different routes to school - both get you there, but one might involve fewer turns and be quicker overall.
Multiple solutions to the same problem
Let's look at a simple example: printing the numbers 1 to 5. Here are three different ways to achieve exactly the same result:
Worked Example: Three Ways to Print Numbers 1-5
Version 1: List each output separately
OUTPUT 1
OUTPUT 2
OUTPUT 3
OUTPUT 4
OUTPUT 5
Version 2: Use a FOR loop
FOR x ← 1 to 5
OUTPUT x
ENDFOR
Version 3: Use a WHILE loop
x ← 1
WHILE x ≤ 5
OUTPUT x
x ← x + 1
ENDWHILE
All three versions produce identical output, but they have different levels of efficiency. If we wanted to print numbers 1 to 100,000, Version 1 would require writing 100,000 separate OUTPUT statements, while Versions 2 and 3 would only need to change one number!
Comparing algorithm efficiency
The efficiency of algorithms becomes more obvious when we compare different approaches to more complex problems. Consider finding the greatest common divisor of two numbers:
Algorithm 1: Euclidean method This uses a mathematical technique that repeatedly subtracts the smaller number from the larger one until zero is reached.
Algorithm 2: Division method This finds the larger number, then tests every possible integer from 1 up to that number to see which ones divide both numbers evenly.
Both algorithms will give the same correct answer, but Algorithm 1 is much more efficient because it requires fewer steps, especially when working with large numbers.
Why efficiency matters
Critical Concept: Scale Matters
The difference in efficiency might seem small when working with small numbers like 10 and 50, but it becomes huge when dealing with numbers in the millions. An inefficient algorithm might take hours to complete a task that an efficient algorithm could finish in seconds.
This is why computer scientists spend time analysing and improving algorithms - small improvements can lead to massive time savings in real-world applications.
Introduction to sorting and searching
Two of the most important types of algorithms in computer science are sorting algorithms and searching algorithms.
A sorting algorithm is a set of instructions designed to arrange a list of values in order (usually from smallest to largest or alphabetically). Once you have a well-designed sorting algorithm, it can be reused to sort any type of data.
A searching algorithm is used to locate a specific value within a list, or to confirm whether that value exists in the list at all. Like sorting algorithms, a good searching algorithm can be applied to find any type of data.
These algorithms are fundamental building blocks that programmers use over and over again in different programmes, which is why understanding their efficiency is so important.
Key Takeaways
Key Points to Remember:
- Algorithm efficiency is measured by counting steps, not time, because computers run at different speeds
- Multiple solutions often exist for the same problem, but they may have very different levels of efficiency
- Efficiency matters more with larger amounts of data - small differences become huge time savings
- Sorting and searching algorithms are reusable tools that form the foundation of many computer programmes
- Choosing the right algorithm can make the difference between a programme that runs in seconds versus hours