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 -

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") [1] https://www.csee.umbc.edu/~olano/s2002c36/ch02.pdf https://www.csee.umbc.edu/~olano/s2002c36/ch02.pdf