I have read that "the computational complexity of the Mersenne twister is O(p2) where p is the degree of the polynomial".
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.