Algorithm Efficiency Edexcel

Algorithm Efficiency

What is algorithm efficiency?

• 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

What is the best case and worst case for a linear search?

• 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

What is the best case and worst case for a binary search?

• 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

What is the best case and worst case for a bubble sort?

• 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

What is the best case and worst case for a merge sort?

• 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