2. What is efficiency
We can measure the efficiency of an algorithm in two ways:
- Time taken - the number of steps in the algorithm
- Space used - the amount of data that the algorithm needs to keep track of at once
Time efficiency is not measuring the number of seconds an algorithm takes to complete. Instead, what this means is how many steps there are in the process before the algorithm can complete its task.
The number of steps required often depends on the input.
For example, it is easier to sort "2 1 3" into ascending order than to sort "3 1 2 5 4 8 3 2 2 1 9".
Time efficiency can be calculated in three different ways:
- Average time to complete
- Worst case time to complete
- Best case time to complete
Think about a list which contains 1,000 items.
The task is to sort this list into ascending order.
Below are are the time efficiency measures of two different algorithms:
|Efficiency measure||Algorithm A||Algorithm B|
|Average time||50 steps||70 steps|
|Best case time||10 steps||10 steps|
|Worst case time||500 steps||250 steps|
Looking at the results, which algorithm is the best?
Well it depends on which measure is important for that particular software program.
If average time is the most important then algorithm A is the best with 50 steps, but if worst case is more important, then algorithm B is twice as fast
This is measuring efficiency in terms of how much memory the algorithm needs to complete its task.
For example, while sorting a list, some algorithms need to remember the entire list at all times, while other algorithms only need to remember the bit that they're working on right now.
Challenge see if you can find out one extra fact on this topic that we haven't already told you
Click on this link: What is algorithm efficiency?