| 100,000 | n log^2^ n| divide and conquer | 2d range trees |
| 50,000 | n^1.585^, n sqrt n| Karatsuba, 'square root trick':blog/square-root-trick |two level tree |
| 1000 - 10,000 | n^2^ | largest empty rectangle, Dijkstra, Prim (on dense graphs) |   |

| 300-500 | n^3^ | all pairs shortest paths, largest sum submatrix,  naive 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 |   |

| 30-50 | n^4^, n^5^, n^6^ |   |   |
| 25 - 40 | 3^n/2^, 2^n/2^ | 'meet in the middle':blog/meet-in-the-middle | hash tables (for set intersection) |
| 15 - 24 | 2^n^ | subset enumeration, brute force, dynamic programming with exponential states |   |