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.
Re:Perlin vs. Simplex
by MillenialMan on Monday July 19, 2021 @06:52AM
(#27881094)
O(n) measures the number of vector operations, but each one operates over a vector, so there are n^2 arithmetic operations. This is also true for perlin noise - there are 2^n vector operations, but the arithmetic complexity is O(n.2^n).
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")
Typo? Simplex noise scales at O(n^2), not O(n).