Join **
36000+
** teachers and students using TTIO.

An algorithm is a step-by-step set of instructions to solve a specific problem and it is important to understand that the same problem can be solved with a variety of algorithms. How can we measure the efficiency of a given algorithm, so it can be compared with a different algorithm which solves the same problem?

That is the amount of (memory) space the algorithm will take up before it terminates with the correct solution.

In order to identify the space-wise efficiency we need to look at the amount of data structures used as the algorithm is running. When considering space-wise efficiency, the aim is to utilise data structures which take up the least amount in memory.

Examples:

- populating a list with variables of type
*real*will be space-wise inefficient, when it is clear that only*whole numbers (integers)*will ever be needed to solve the problem. - initialising an array with a length of 1000 will be space-wise inefficient, when it is clear that the maximum elements to be stores will be 100.

This is the amount of time it takes for the algorithm to terminate with the correct solution.

Any measure of time will depend on other factors, like

- the particular version and type of programming language used to implement the algorithm;
- the hardware specification on which the implementation will be running;
- and of course the input to the algorithm, e.g. searching through a very very large set will take longer that searching through a short set and searching for an item which does not exist in a set will take longer than searching for an item which is present in a given set.

Algorithm | Data Structure | Time Complexity | ||
---|---|---|---|---|

Best | Average | Worst | ||

Quicksort | Array | `O(n log(n))` |
`O(n log(n))` |
`O(n^2)` |

Mergesort | Array | `O(n log(n))` |
`O(n log(n))` |
`O(n log(n))` |

Heapsort | Array | `O(n log(n))` |
`O(n log(n))` |
`O(n log(n))` |

Bubble Sort | Array | `O(n)` |
`O(n^2)` |
`O(n^2)` |

Insertion Sort | Array | `O(n)` |
`O(n^2)` |
`O(n^2)` |

Select Sort | Array | `O(n^2)` |
`O(n^2)` |
`O(n^2)` |

Bucket Sort | Array | ```
O(n+k)
``` |