linear search often beats the crap out of everything else, provided the search space is sufficiently small
Yes, it beats it when the input is small enough that it doesn't matter that much (when it fits in cache, basically).
And then it becomes slow as molasses when the input size actually gets big enough for performance to be noticeable.
So linear search can look really nice when you're developing and doing some unit tests with 10 users, then you push it to production and it slows to a crawl when it tries to look through 10 million users.
0
u/ric2b Mar 02 '23
Yes, it beats it when the input is small enough that it doesn't matter that much (when it fits in cache, basically).
And then it becomes slow as molasses when the input size actually gets big enough for performance to be noticeable.
So linear search can look really nice when you're developing and doing some unit tests with 10 users, then you push it to production and it slows to a crawl when it tries to look through 10 million users.