What is the time complexity of the Mersenne twister?

Question

I have read that "the computational complexity of the Mersenne twister is O(p²) where p is the degree of the polynomial".

• What does this mean?
• Which polynomial is this referring to?
• Also, is computational complexity another way of saying time complexity, or does this have to do with the amount of space the algorithm takes to run?

Answer 1

Generating 2 n random numbers takes twice as long as generating n random numbers, so the time complexity of Mersenne Twister is O(1), meaning that it takes a constant amount of time to generate a single random number; note that this is probably amortized complexity, as Mersenne Twister generally computes a batch of random numbers then doles them out one at a time until the batch is consumed, at which time it computes more. The Google search that you reference is saying the same thing, although it tries to more precisely determine the constant. Computational complexity generally refers to time complexity, though in some contexts it could also refer to space complexity.