Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is Big-O notation always reliable?

For example:

Algorithm A: $n * 10^{100} = \mathcal{O}\left(n\right)$

Algorithm B: $n^{1.001} = \mathcal{O}\left(n^{1.001}\right)$

According to Big-$\mathcal{O}$ notation, Algorithm $A$ would be more efficient, yet for all practical purposes Algorithm $B$ is more efficient. In a situation like this, wouldn't Big-O notation fail? Is there a way to avoid such problems?

share|improve this question
12  
The notation is "reliable", in that it denotes a perfectly consistent, well-defined mathematical idea. It just doesn't provide the information you would like it to provide. –  Zev Chonoles May 12 '12 at 20:51
5  
Theoretically $n \times 10^{100}$ is still better than $n^{1.001}$ for large enough $n$. On the other hand, practical computer science is hardly a part mathematics. –  Levon Haykazyan May 12 '12 at 20:52
6  
Asymptotic complexity analysis is seldom about practice. It is, as the name implies, about asymptotic behaviour of the algorithm. In practice, however, constants and lower order terms matter. Most interesting numerical packages will select between a pack of different algorithms based on the input size and properties. –  user2468 May 12 '12 at 21:15
1  
To use a particularly common example: Quicksort is asymptotically the most efficient sorting algorithm, but for small data sets, one usually prefers to use insertion sort or Shell's sort, since they do slightly better than Quicksort for small $n$, even if they are $O(n^\alpha)$ methods as opposed to Quicksort's $O(n\log\,n)$. –  J. M. May 13 '12 at 5:16
1  
Just a note -- by putting in an explicit constant you have departed from correct $\mathcal{O}\left(\right)$ usage and are implying that $n * 10^{100}$ is the actual complexity function, not just the $\mathcal{O}()$. –  David Lewis May 13 '12 at 11:30
add comment

4 Answers

up vote 8 down vote accepted

The concept involves "when $n$ is large". The antidote to your problem involves noticing that "large enough to be 'large'" varies between contexts (sometimes 2 is large enough). It looks like your context is too small to be "large" ... and this always needs checking.

share|improve this answer
add comment

this concept (that the big O notation is useless for small $n$) is known and why tuning of algorithms for specific $n$s happens

for example insertion sorting 5 elements in place is faster that using quicksort and this is why many implementations have a if(length<5)do insertion sort guard clause in the recursion

in your example this would mean that you would switch algorithms depending on whether $n^{1.001} \lt 100*n$ or $n\lt100^{100}$

share|improve this answer
add comment

This should be a comment, but there isn't enough room.

There are a number of real life problems where the distinction between fastest theoretical runtime and fastest practical algorithm is apparent. The simplest example I know of is matrix multiplication.

Multiplying two $n\times n$ square matrices is obviously at least $O(n^2)$, but with the algorithm that comes strait from the definition it is $O(n^3)$. For practical purposes, the best algorithm is the Strassen Algorithm in most cases, which is approximately $O(n^{2.807})$. The fastest known algorithm in theory is the Coppersmith–Winograd algorithm, at a much faster $O(n^{2.3727})$. But in practice, the smallest matrices for which this is actually faster than the Strassen algorithm are large enough that they just can't be multiplied on modern computers, regardless of what algorithm you pick.

Incidentally, it's suspected that one can have $O(n^2)$ matrix multiplication (perhaps with some extra sublinear factors), but how to do it has been open for a long time.

So, if by $O$ being reliable, you mean that the fastest algorithm in theory is actually the most useful for practical data sets, the answer is no. On the other hand, what is practically useful is much harder to define, which is why $O$ and its variants are the ways people usually study algorithms.

share|improve this answer
    
2.3737 was recently improved to 2.3727 (see Wikipedia) –  sdcvvc May 15 '12 at 23:13
    
Thanks, I wasn't aware of that. –  Logan Maingi May 15 '12 at 23:18
add comment

For any two algorithms with different order (big-$\mathcal{O}$) complexity, we can calculate the actual ratio of their complexity as a function of n. Being a bit more general in your case by using symbolic constants, and assuming there are no other constant multiplicative or additive factors, we get

$R=$ exponential/linear $=n^b/{(n\cdot 10^a)}=n^{b-1}/10^a$, with $a=100, b=1.001$ for your example

Calculate the "crossover point" by setting $R=1$ and solving, giving

$n=10^{a/{(b-1)}}$.

Plug in your values and you get that these two algorithms "cross" at

$n=10^{100/.001}=10^{100000}$ or 10 followed by 100,000 zeros.

Indeed that's an astronomically large number, nope, even bigger than astronomical, probably one of those silly metaphors like more than the number of electrons if all of known space were packed tightly with them. So, yes, anything even remotely practical should be done with the "exponential" algorithm in this case.

But if $a = .5, b = 1.1$ you'd get the crossover at $n=10^5=$ 100,000. So, if $n>$ 100,000 you'd prefer the linear algorithm, and if $n=$ 1,000,000, which is not at all unreasonable, the linear algorithm is faster by a factor of $R \approx$ 7.96, and the ratio grows exponentially for larger $n$.

So, yes, $\mathcal{O}$ analysis is quite reliable, and a very useful tool for evaluating algorithms.

share|improve this answer
1  
how do you get from $1=\frac{n^{0.001}}{100}$ to $n=10^\frac{100}{0.001}$? –  ratchet freak May 13 '12 at 1:04
    
Whoops -- confused $a$ and $10^a$ in the eqn for R. Fixed. –  David Lewis May 13 '12 at 5:11
    
it's still wrong $100=10^2$ so $a$ should be equal to $2$ not $100$ –  ratchet freak May 13 '12 at 8:56
    
@ratchet freak -- Now you have got them confused -- heh heh. The constant in the OP is $10^{100}$, not $10^2$. –  David Lewis May 13 '12 at 11:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.