Please tick the below box to proceed
I agree (or if I am under 13 my parent or guardian agrees on my behalf) to the terms and conditions of use and that:
- My test statistics may be published on the site leaderboard against my username
- My teacher(s) can review my test scores
- I can receive feedback on my tests from my teacher(s)
Please tick this box to proceed
Say you were making a cup of tea ...now, 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.
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"
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).
|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.|
|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.|
|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.|
|linearithmic, loglinear, or quasilinear||Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort|