Difference between revisions of "Hidden constant factor"
From PEGWiki
(Created page with "When the time or space required for an algorithm is expressed in terms of the input size using big O notation, constant factors are destroyed. For example, if one algorithm r...") |
m (invisible -> hidden (post-move)) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | When the time or space required for an [[algorithm]] is expressed in terms of the input size using big O notation, constant factors are destroyed. For example, if one algorithm requires <math>n^2</math> nanoseconds on a given machine, and another requires <math>2n^2</math> nanoseconds on that machine, then both algorithms are <math>O(n^2)</math>, and from that information alone we cannot determine that the latter is faster than the former. That is, in big O notation, the constant factor is ''' | + | When the time or space required for an [[algorithm]] is expressed in terms of the input size using big O notation, constant factors are destroyed. For example, if one algorithm requires <math>n^2</math> nanoseconds on a given machine, and another requires <math>2n^2</math> nanoseconds on that machine, then both algorithms are <math>O(n^2)</math>, and from that information alone we cannot determine that the latter is faster than the former. That is, in big O notation, the constant factor is '''hidden'''. |
| − | From a theoretical point of view, this is advantageous, since we could always design a faster machine, which would make our algorithms take less time to run, but that wouldn't reflect the efficiency of the algorithm itself; and so we always want to discard the constant factor. In practice, however, the | + | From a theoretical point of view, this is advantageous, since we could always design a faster machine, which would make our algorithms take less time to run, but that wouldn't reflect the efficiency of the algorithm itself; and so we always want to discard the constant factor. In practice, however, the hidden constant factor is very important. If one algorithm requires <math>n^2</math> nanoseconds and another requires <math>n</math> milliseconds, then the latter appears to be more efficient as it is <math>O(n)</math> rather than <math>O(n^2)</math>, but in practice is only faster when <math>n > 10^6</math>. |
| − | The discrepancy in | + | The discrepancy in hidden constant factor between two algorithms with the same asymptotic running time (big O) is a consequence of three main factors: |
* Some algorithms, by nature, simply require more operations than others. [[Bubble sort]], for example, tends to use more operations than [[insertion sort]]. Bubble sort can only reorder elements by swapping two adjacent elements at a time, and swapping two elements requires three copy operations (as an intermediate variable has to be used), and swapping two elements eliminates an inversion from the sequence. On the other hand, insertion sort moves elements longer distances at once. When an element is moved <math>m</math> positions, it eliminates <math>m</math> inversions, and requires <math>m+2</math> copy operations; and thus will insertion sort will generally average a bit more than one copy operation per inversion. | * Some algorithms, by nature, simply require more operations than others. [[Bubble sort]], for example, tends to use more operations than [[insertion sort]]. Bubble sort can only reorder elements by swapping two adjacent elements at a time, and swapping two elements requires three copy operations (as an intermediate variable has to be used), and swapping two elements eliminates an inversion from the sequence. On the other hand, insertion sort moves elements longer distances at once. When an element is moved <math>m</math> positions, it eliminates <math>m</math> inversions, and requires <math>m+2</math> copy operations; and thus will insertion sort will generally average a bit more than one copy operation per inversion. | ||
| − | * Some operations are slower than others. For example, multiplication and division of floating point numbers tends to be slower than addition and subtraction. Thus, for example, if a primitive in [[computational geometry]] can be implemented using either six additions and two multiplications or four additions and three multiplications, both implementations take constant time, but the | + | * Some operations are slower than others. For example, multiplication and division of floating point numbers tends to be slower than addition and subtraction. Thus, for example, if a primitive in [[computational geometry]] can be implemented using either six additions and two multiplications or four additions and three multiplications, both implementations take constant time, but the former is probably faster. |
* Some algorithms exhibit better locality of reference than others. For example, two nested for loops that iterate over a two-dimensional [[array]] should always be written so that they access the elements of the array in sequence in RAM, rather than in the other order. For example, in C this means that they should access elements in the other <code>A[0][0], A[0][1], A[0][2], ..., A[1][0], ...</code> rather than in the order <code>A[0][0], A[1][0], A[2][0], ..., A[0][1], ...</code>. The former hits the cache on almost every access; the latter always misses it. | * Some algorithms exhibit better locality of reference than others. For example, two nested for loops that iterate over a two-dimensional [[array]] should always be written so that they access the elements of the array in sequence in RAM, rather than in the other order. For example, in C this means that they should access elements in the other <code>A[0][0], A[0][1], A[0][2], ..., A[1][0], ...</code> rather than in the order <code>A[0][0], A[1][0], A[2][0], ..., A[0][1], ...</code>. The former hits the cache on almost every access; the latter always misses it. | ||
| − | Here are some general useful conclusions that can be drawn about the | + | Here are some general useful conclusions that can be drawn about the hidden constant factor: |
* [[Quicksort]] is generally faster than [[heapsort]] and [[mergesort]], though each has average-case performance <math>O(n \log n)</math>. Furthermore, most programming language standard libraries include highly optimized sorting routines. The <math>O(n \log n)</math> time required to sort generally has a lower constant factor than almost any other <math>O(n \log n)</math> algorithm you might want to implement for the same input. | * [[Quicksort]] is generally faster than [[heapsort]] and [[mergesort]], though each has average-case performance <math>O(n \log n)</math>. Furthermore, most programming language standard libraries include highly optimized sorting routines. The <math>O(n \log n)</math> time required to sort generally has a lower constant factor than almost any other <math>O(n \log n)</math> algorithm you might want to implement for the same input. | ||
* The <math>O(\log n)</math> time associated with a [[binary heap]] operation generally has lower constant factor (is faster) than the <math>O(\log n)</math> time associated with a [[balanced binary search tree]] operation. Thus, BBSTs implement a superset of the functionality of heaps, but at the cost of slower running time. | * The <math>O(\log n)</math> time associated with a [[binary heap]] operation generally has lower constant factor (is faster) than the <math>O(\log n)</math> time associated with a [[balanced binary search tree]] operation. Thus, BBSTs implement a superset of the functionality of heaps, but at the cost of slower running time. | ||
* [[Segment tree]]s require about twice as much memory as [[binary indexed tree]]s (and incur an additional factor of 2 for each additional dimension), and an <math>O(\log n)</math> segment tree operation is generally slower than an <math>O(\log n)</math> BIT operation, too. | * [[Segment tree]]s require about twice as much memory as [[binary indexed tree]]s (and incur an additional factor of 2 for each additional dimension), and an <math>O(\log n)</math> segment tree operation is generally slower than an <math>O(\log n)</math> BIT operation, too. | ||
* [[Suffix tree]]s use more memory and take more time to construct than [[suffix array]]s, though both are linear. | * [[Suffix tree]]s use more memory and take more time to construct than [[suffix array]]s, though both are linear. | ||
Latest revision as of 08:49, 18 February 2012
When the time or space required for an algorithm is expressed in terms of the input size using big O notation, constant factors are destroyed. For example, if one algorithm requires 
nanoseconds on a given machine, and another requires 
nanoseconds on that machine, then both algorithms are 
, and from that information alone we cannot determine that the latter is faster than the former. That is, in big O notation, the constant factor is hidden.
From a theoretical point of view, this is advantageous, since we could always design a faster machine, which would make our algorithms take less time to run, but that wouldn't reflect the efficiency of the algorithm itself; and so we always want to discard the constant factor. In practice, however, the hidden constant factor is very important. If one algorithm requires nanoseconds and another requires 
milliseconds, then the latter appears to be more efficient as it is 
rather than , but in practice is only faster when 
.
The discrepancy in hidden constant factor between two algorithms with the same asymptotic running time (big O) is a consequence of three main factors:
- Some algorithms, by nature, simply require more operations than others. Bubble sort, for example, tends to use more operations than insertion sort. Bubble sort can only reorder elements by swapping two adjacent elements at a time, and swapping two elements requires three copy operations (as an intermediate variable has to be used), and swapping two elements eliminates an inversion from the sequence. On the other hand, insertion sort moves elements longer distances at once. When an element is moved
positions, it eliminates inversions, and requires 
copy operations; and thus will insertion sort will generally average a bit more than one copy operation per inversion. - Some operations are slower than others. For example, multiplication and division of floating point numbers tends to be slower than addition and subtraction. Thus, for example, if a primitive in computational geometry can be implemented using either six additions and two multiplications or four additions and three multiplications, both implementations take constant time, but the former is probably faster.
- Some algorithms exhibit better locality of reference than others. For example, two nested for loops that iterate over a two-dimensional array should always be written so that they access the elements of the array in sequence in RAM, rather than in the other order. For example, in C this means that they should access elements in the other
A[0][0], A[0][1], A[0][2], ..., A[1][0], ...rather than in the orderA[0][0], A[1][0], A[2][0], ..., A[0][1], .... The former hits the cache on almost every access; the latter always misses it.
Here are some general useful conclusions that can be drawn about the hidden constant factor:
- Quicksort is generally faster than heapsort and mergesort, though each has average-case performance
. Furthermore, most programming language standard libraries include highly optimized sorting routines. The time required to sort generally has a lower constant factor than almost any other algorithm you might want to implement for the same input. - The
time associated with a binary heap operation generally has lower constant factor (is faster) than the time associated with a balanced binary search tree operation. Thus, BBSTs implement a superset of the functionality of heaps, but at the cost of slower running time. - Segment trees require about twice as much memory as binary indexed trees (and incur an additional factor of 2 for each additional dimension), and an segment tree operation is generally slower than an BIT operation, too.
- Suffix trees use more memory and take more time to construct than suffix arrays, though both are linear.
