For example, a brute force combinatorial solution to a problem written in C or assembler can outstrip an 'intelligent' algorithm written in perl, even though the former rates as O(n*m) and the latter O(n) or even O(log n).O() is concerned with the asymptotic behavior of an algorithm, that is, "in the limit" as the "size" of the input approaches infinity. There is an implied (and generally unspecified) constant associated with any O() statement:
The running time of FOO is O(n).translates roughly to
For sufficiently large n, the running time of FOO is very close to C*n, where C is an arbitrary constant.Since the theory is concerned with n larger than anything practical, it doesn't matter what C turns out to be.
But in practice, for reasonable inputs (e.g., inputs that the algorithm can finish before the predicted end of the Universe), C can compete with the O() term. If FOO is O(n), and n == 100, but C == 100, then FOO, for practical purposes, appears to be O(n2). It is only when n approaches ~1000 that FOO appears to behave more like O(n).
In summary, for practical problems, the constant C is not arbitrary, and cannot be dismissed without scrutiny.
In Theory, Theory is sufficient. In Practice, it's not.
-QM
--
Quantum Mechanics: The dreams stuff is made of
In reply to Re:^6: Data structure challenge
by QM
in thread Data structure challenge
by Abigail-II
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |