points by choeger 3 days ago | 0 comments
I am long out of this game, but the complexity class they show still has an n in the exponent, even if divided by log(n).
I have no intuition whatsoever on how that algorithm scales. Can anyone enlighten me?
[–] punty 2 days ago
2^(n/logn) will eventually be smaller than (1+epsilon)^n for any fixed positive epsilon. However, as log(n) grows quite slowly n will have to be exceptionally large. For epsilon=2^-D n will have to be something like 2^(2^D) large.
[–] SkiFire13 2 days ago