Comment by afdbcreid
2 hours ago
If the table size is constant, no matter how large, then it is correct and important (even if useless; the existing n*log(n) algorithm is already useless).
2 hours ago
If the table size is constant, no matter how large, then it is correct and important (even if useless; the existing n*log(n) algorithm is already useless).
I honestly think there’s a lot of fuzziness possible in complexity theory because of things like this. Yes you can skip some portions of a calculation and rightfully so by the current established formalisation of complexity theory but i think under another formalisation we’d probably see these nlogn^0.999999 cases become more clearly nlogn.