Preview lessons, content and tests

Computer Science & Programming solved. All in one platform.

1. To trial the platform and take tests, please take a few seconds to SIGN UP and SET UP FREE.
2. Searching for something specific? See our text overview of all tests. Includes 'real teacher' use videos.

Algorithm Efficiency

Say you were making a cup of tea, ordinarily you wouldn't need to follow an algorithm to make said cup of tea, but suppose you were a robot and needed instructions ... consider for a moment how important the efficiency of the algorithm would be.

What do we mean by efficiency?

Well, we mean things like TIME and SPACE and often times these two things have a big influence on each other. Definition: Algorithmic efficiency are the properties of an algorithm which relate to the amount of computational resources used by the algorithm. Analgorithm must be analysed to determine its resource usage.

The importance of efficiency with respect to time was emphasised by Ada Lovelace in 1843 as applying to Charles Babbage's mechanical analytical engine:

"In almost every computation a great variety of arrangements for the succession of the processes is possible, and various considerations must influence the selections amongst them for the purposes of a calculating engine. One essential object is to choose that arrangement which shall tend to reduce to a minimum the time necessary for completing the calculation"

Theoretical analysis

In the theoretical analysis of algorithms, the normal practice is to estimate their complexity in the asymptotic sense, i.e. use Big O notation to represent the complexity of an algorithm as a function of the size of the input n. This is generally sufficiently accurate when n is large, but may be misleading for small values of n (e.g. bubble sort may be faster than quicksort when only a few items are to be sorted).

Some examples of Big O notation include:

Notation Name Examples
O(1)\, constant Determining if a number is even or odd; Using a constant-size lookup table; Using a suitable hash function for looking up an item.
O(\log n)\, logarithmic Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap.
O(n)\, linear Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers by ripple carry.
O(n\log n)\, linearithmic, loglinear, or quasilinear Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
O(n^{2})\, -->