| 10,000,000 | n, n log log n, n log* n | set intersection, Eratosthenes sieve, radix sort, KMP, topological sort, Euler tour, strongly connected components, 2sat | disjoint sets, tries, hash_map, 'rolling hash':blog/rolling-hash |
| 1,000,000,000 | log n, sqrt n | binary search, ternary search, fast exponentiation, euclid algorithm | |
These numbers aren't very precise, they assume in memory operations and some varying constant factors, but they do give a good starting point in your search for a solution that fits your problem and your data size.
There are a few caveats, these numbers aren't very precise, they assume in memory operations and some varying constant factors. But they do give a good starting point in searching for an algorithm that fits your problem and your data well.
