Hm, not a typo, I thought it was O(n) since that's how simplices scale with dimensions. Where does the extra *n come from? I guess identifying the right simplex isn't free..
Right, the gradients will still have more dimensions to evaluate.
Right, the gradients will still have more dimensions to evaluate.
Obviously this ignores the parallelizability of the algorithms, which is probably the more important factor at this point, and the ability to be hardware accelerated.
(Edit: the complexity is outlined on page 20 of the original simplex noise paper[1]. Just ctrl+f "complexity")