Complexity of the Fisher-Yates Shuffle Algorithm This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n).

In each iteration i, a random integer is chosen between 1 and i. Simply writing the integer in memory is O(log i), and since there are n iterations, the total is

O(log 1) + O(log 2) + ... + O(log n) = O(n log n)

which isn't better the the naive algorithm. Am I missing something here?

Note: The naive algorithm is to assign each element a random number in the interval (0,1) , then sort the array with regard to the assigned numbers.
I suspect that here, like in most algorithms work, the cost of reading and writing $O(\log n)$ bit numbers is assumed to be a constant. It's a minor sin, as long as you don't get carried away and collapse P and PSPACE by accident.