Editing Hidden constant factor
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| 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 '''invisible'''. |
| − | 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 invisible 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 invisible 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 former is probably faster. | * 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 invisible 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. | ||
