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?