I guess you have to distinguish between # of elements vs the max bit-width of a an element. But if you're leaving the constant-memory access model (where you can assume each element fits in memory and all arithmetic on them is constant time), then doesn't it take O(n log k) (k is the numeric value of the maximum element, n is total number of elements) to simplify write out the array? You physically can't do O(n) [ignoring the k]

Maybe relevant comments [1, 2, 3]

[1] https://news.ycombinator.com/item?id=44854520 [2] https://news.ycombinator.com/item?id=43005468 [3] https://news.ycombinator.com/item?id=45214106