Algorithm Efficiency (AQA GCSE Computer Science)

Revision Note

Test yourself

Written by: James Woodhouse

Reviewed by: Lucy Kirkham

Algorithm Efficiency

What is algorithm efficiency?

Algorithm efficiency is how much time 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

Efficiency in action

If we took the numbers 1-20 jumbled up in a list
How efficient an algorithm is would be determined by how quickly it could sort the numbers into ascending order

Sort 1 (Bubble sort)	Sort 2 (Insertion sort)
`DEFINE listToSort AS a list of integers containing the numbers 1 to 20` `SET lengthOfList TO the length of listToSort` `FOR currentIndex FROM 0 TO lengthOfList - 1 DO` `FOR innerIndex FROM 0 TO lengthOfList - 1 - currentIndex DO` `IF listToSort[innerIndex] > listToSort[innerIndex + 1] THEN` `TEMP ← listToSort[innerIndex]` `listToSort[innerIndex] ← listToSort[innerIndex + 1]` `listToSort[innerIndex + 1] ← TEMP` `END IF` `END FOR` `END FOR`	`DEFINE listToSort AS a list of integers containing the numbers 1 to 20` `SET lengthOfList TO the length of listToSort` `FOR currentIndex FROM 1 TO lengthOfList - 1 DO` `SET currentValue TO listToSort[currentIndex]` `SET innerIndex TO currentIndex - 1` `WHILE innerIndex >= 0 AND listToSort[innerIndex] > currentValue DO` `listToSort[innerIndex + 1] ← listToSort[innerIndex]` `SET innerIndex TO innerIndex - 1` `END WHILE` `listToSort[innerIndex + 1] ← currentValue` `END FOR`

Sort 1 (Bubble sort)

Sort 2 (Insertion sort)

DEFINE listToSort AS a list of integers containing the numbers 1 to 20

SET lengthOfList TO the length of listToSort

FOR currentIndex FROM 0 TO lengthOfList - 1 DO

FOR innerIndex FROM 0 TO lengthOfList - 1 - currentIndex DO

IF listToSort[innerIndex] > listToSort[innerIndex + 1] THEN

TEMP ← listToSort[innerIndex]

listToSort[innerIndex] ← listToSort[innerIndex + 1]

listToSort[innerIndex + 1] ← TEMP

END IF

END FOR

DEFINE listToSort AS a list of integers containing the numbers 1 to 20

SET lengthOfList TO the length of listToSort

FOR currentIndex FROM 1 TO lengthOfList - 1 DO

SET currentValue TO listToSort[currentIndex]

SET innerIndex TO currentIndex - 1

WHILE innerIndex >= 0 AND listToSort[innerIndex] > currentValue DO

listToSort[innerIndex + 1] ← listToSort[innerIndex]

SET innerIndex TO innerIndex - 1

END WHILE

listToSort[innerIndex + 1] ← currentValue

END FOR

In the algorithms above, the worst case of a bubble sort is that it would take 361 comparisons to sort 20 items of data
The worst case of an insertion sort with 20 items is that it would perform 190 comparisons
This means that in this instance, although both algorithms perform the same job and achieve the same result, an insertion sort would be significantly faster because it is much more efficient in how it uses the computer’s processing power and memory

Last updated: 27 September 2024

You've read 0 of your 10 free revision notes

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

Test yourself

Did this page help you?

Previous:Tracing AlgorithmsNext:Linear Search