teach-ict.com logo

THE education site for computer science and ICT

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

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

Example

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:

Compare 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

 

Space efficiency

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?