3 ms·
>I think the takeaway from this article is not to blindly trust the theoretical big-O numbers for data structures and actually test them with realistic datasets
by pedrocr 10y ago
>I think the takeaway from this article is not to blindly trust the theoretical big-O numbers for data structures and actually test them with realistic datasets on your target hardware.
You have to do this anyway to make sure that the constant factors aren't big enough to change the optimal approach at the size of your dataset. Big-O only really buys you an initial rule to not do things that are obviously wrong.
- wongarsu 10y agoRight, an algorithm that always produces an answer right after the heat death of the universe is O(1). Big-O is great for telling you which algorithms/datastructures won't scale, it can't tell you which are actually fast enough.
- wtetzner 10y agoAnd in fact, some data structures that scale poorly will perform better on small sets of data. For example, a simple list of pairs with linear lookup time can be faster than a hash table for small amounts of data, because it doesn't have to compute the hash.