Algorithmic efficiency

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, algorithmic efficiency is a property of an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> which relates to the amount of <a href="/facts/Computational_resource/YyleNx71">computational resources</a> used by the algorithm. Algorithmic efficiency can be thought of as analogous to engineering <a href="/facts/Productivity/yXlzAjC2">productivity</a> for a repeating or continuous process.
For maximum efficiency it is desirable to minimize resource usage. However, different resources such as <a href="/facts/Time_complexity/77T62gmf">time</a> and <a href="/facts/Space_complexity/nsnAW5cV">space</a> complexity cannot be compared directly, so which of two algorithms is considered to be more efficient often depends on which measure of efficiency is considered most important.
For example, <a href="/facts/Cycle_sort/JWzhwyNP">cycle sort</a> and <a href="/facts/Timsort/llcssLEF">timsort</a> are both <a href="/facts/Sorting_algorithm/PwHpj1Gs">algorithms to sort a list</a> of items from smallest to largest. Cycle sort organizes the list in time proportional to the number of elements squared (
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\textstyle O(n^{2})}
 
, see <a href="/facts/Big_O_notation/weFFjSWg">Big O notation</a>), but minimizes the writes to the original array and only requires a small amount of extra <a href="/facts/Computer_memory/hQKVQ51J">memory</a> which is constant with respect to the length of the list (
 
 
 
 O
 (
 1
 )
 
 
 {\textstyle O(1)}
 
). Timsort sorts the list in time <a href="/facts/Linearithmic/77T62gmf">linearithmic</a> (proportional to a quantity times its logarithm) in the list's length (
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\textstyle O(n\log n)}
 
), but has a space requirement <a href="/facts/Proportionality_(mathematics)/xDQmfh6t">linear</a> in the length of the list (
 
 
 
 O
 (
 n
 )
 
 
 {\textstyle O(n)}
 
). If large lists must be sorted at high speed for a given application, timsort is a better choice; however, if minimizing the <a href="/facts/Flash_memory/Cn8JsStx">program/erase cycles</a> and <a href="/facts/Memory_footprint/wnS6TgpY">memory footprint</a> of the sorting is more important, cycle sort is a better choice.

Algorithmic efficiency open-in-new

Algorithmic efficiency