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:

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.