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.