4 ms·
O(1) means bounded by a constant upper bound, not that every actual run of the program takes the exact same amount of time. Just like "simple quick sort is O(n^
by tom_mellior 9y ago
O(1) means bounded by a constant upper bound, not that every actual run of the program takes the exact same amount of time. Just like "simple quick sort is O(n^2)" does not mean that every invocation will take a quadratic amount of time. The parent's "can be solved in constant time" means the same thing, informally.
Anyway, we are in agreement that enumerating all boards would be quite inefficient.
- dahart 9y agoAre you claiming that all sudoku solvers are constant time algorithms, because the upper bound is not greater than enumerating the total constant number of boards? There are no O(1) sudoku solvers in existence that run in a short amount of time, yet you seem to be suggesting that the "very simple" sudoku solvers you referred to can be classified as O(1) algorithms.
- tom_mellior 9y agoI'm claiming it's possible to write Sudoku solvers that have some constant upper bound on execution time. If you read this as "a short amount of time", you are misreading it. I'm also not saying that this is true for all Sudoku solvers, since you could write one that sometimes just decides to uselessly burn cycles for a few centuries before returning a correct solution. Here's that simple argument again: Sudoku can be solved in time at most exponential in the input size. The input size of 9x9 Sudoku is constant. The exponential of that constant is a constant. Not a very interesting argument? I agree, so I'm dropping this now.