| 15 - 25 | 2^n^ | subset enumeration, brute force, dynamic programming with exponential states | |
| 25 - 40 | 3^n/2^, 2^n/2^ | 'meet in the middle':blog/meet-in-the-middle | hash tables (for set intersection) |
| 30-50 | n^4^, n^5^, n^6^ | | |
| 300-700 | n^3^ | all pairs shortest paths, largest sum submatrix, matrix multiplication, matrix chain multiplication, network flow | |
| 300-500 | n^3^ | all pairs shortest paths, largest sum submatrix, matrix multiplication, matrix chain multiplication, network flow | |
| 1000 - 10000 | n^2^ | largest empty rectangle, Dijkstra, Prim (on dense graphs) | |
| 30000 | n sqrt n | 'square root trick':blog/square-root-trick |two level tree |
| 60000 | n log^2^ n, n^log 3^ | divide and conquer, Karatsuba | 2d range trees |
| 60000 | n log^2^ n, n^log~2~3^ | divide and conquer, Karatsuba | 2d range trees |
| 100000 | n log n | divide and conquer, sweep line, Kruskal, Dijkstra | segment trees, range trees, heaps, treaps, binary indexed trees, suffix arrays |
| 1000000 | 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 |
| 1000000000 | log(n), sqrt(n) | binary search, ternary search, fast exponentiation, euclid algorithm | |
