On Friday, 4 December 2015 at 09:17:07 UTC, Ola Fosheim Grøstad
wrote:
On Friday, 4 December 2015 at 09:09:35 UTC, ZombineDev wrote:
and space complexity (the correctness is given). Otherwise,
designing large systems becomes impossible, because all large
systems have hard performance requirements.
I am sorry to say this, but hard performance requirements
require O(1) on everything.
Only when dealing with an arbitrary number of elements. O(n^2)
could be fine if you know for a fact that you're always dealing
with a very small number of elements. And some algorithms with
worse complexity are actually faster than algorithms with lower
complexity when dealing with a small number of elements -
particularly since with a small number of elements, the
coefficients can matter a lot more than n. So, really, to know
which algorithm is appropriate, you need to know how it's
actually going to be used in the program in question and how
different algorithms perform there. O(1) is definitely better,
but it's not necessarily required.
But yes, if you're dealing with an arbitrarily large number of
elements, anything worse than O(1) isn't going to cut it if you
have hard performance requirements.
Big-Oh tells you essentially very little if it is more than
O(1). Quick sort and insertion sort are O(N^2), bucket sort is
O(N). That does not make bucket sort faster than quick sort or
even insertion sort on a specific case as it is dominated by
the number of possible values.
Yeah. Really, Big-Oh tells you something about the worst case
with an arbitrary number of elements. What actually happens in
the program depends heavily on the number of elements which are
actually involved. With large numbers of elements, Big-Oh starts
mattering, but if the number of elements isn't large, then
coefficients and minor implementation details of an algorithm
start mattering a lot more than its conceptual worst case.
Still, in general, it's better to be aware of algorithmic
complexity and favor algorithms with lower complexity until you
need to optimize the code based on your specific use case and
determine that a higher complexity algorithm actually performs
better in that specific use case.
- Jonathan M Davis
