| That is another very interesting part of complexity theory, yeah. Like, "Constant time" means, "Runtime independent from input". And, well, solving any sudoku of size 9 or less is a constant times 6.6e21. Maybe a bit more in the exponent, but meh. Like in graph theory, there are some algorithms for I think maxflow, which solve the thing in O(node_count^4). Theory can push this down to like O(node_count^3) or O(node_count^2.7) or less. That's amazing - you can lose almost 2 orders of magnitude. Well, implementation of these algorithms and more detailed analysis point out _huge_ precomputations necessary to achieve the speedups. In practice, you'd only see speedups if you had graphs with multiple billions of nodes. In practice, if you deal with a boring subset like "realistically relevant", asymptotically worse algorithms may be the objectively better choice. Like in this case. Here, some O(n^5) - O(n^9) depending on what the solver does can be better than O(1) for many practical purposes. In such areas, intuition is little more than a lie. |