Algorithm Efficiency (Edexcel GCSE Computer Science)

Revision Note

Author

Expertise

Computer Science

Algorithm efficiency is how much time and memory it takes to complete an algorithm
In programming, there is often more than one algorithm which can solve a problem
An example of this is a linear search and binary search as both find a value in a list, however, depending on the circumstances, one may be much faster than the other
For the example comparison, we will use the following dataset

The best case for a linear search is that the item being looked for is the first item in the list
The worst case is that the item is the last element in the data set or that it is not present at all
As a result of a linear search checking each item from the first item and incrementing to the next item, a list of 1000 items would require 1000 searches if the data item was the last in the list
The negative of a linear search is that it has to pass through the entire data set to search each item until the item is found

The best case for a binary search is that the item being looked at is found after one comparison
The worst case is that the item is the last comparison, and in the list above of 7 items would be after 3 searches
As a result of a binary search being performed through divide and conquer, the main positive is that even if the data item was the last to be looked at the last position in a list of 1000 items, it would require 10 searches because it does not need to check each data item
In this instance, a binary search is significantly more effective and efficient at finding the target data
Remember that the precondition for a binary search is that the data must be sorted before performing the search, the data set above would have to appear like below

The best case for a bubble sort is that the data is already in order or almost in order
The worst case for a bubble sort is that the data is in the opposite order to its sorted version
- For example, a user wants the data sorted in ascending order but the data is in descending order before the sort begins

The best case for a merge sort is that the data is already in order or almost in order
The worst case for a merge sort gets a little more complicated due to the way the algorithm works
The merge sort is an out-of-place algorithm, meaning that extra memory is required to move the data round
The amount of memory necessary depends on the size of the data
The reason for this is because it splits the data before merging it back in a sorted manner
Beyond this explanation the content strays outside of the GCSE exam and towards A Level content around Big O notation

to absolutely everything:

the (exam) results speak for themselves:

Did this page help you?