n can be any number, therefore a counter is of size log(n). The condition says you may have a limited number of storage units, each han hold a number no more than n.

This is much clearer. The original phrase is a little misleading. The phrase seemed that we need to allocate an array of size log(n) of integer type (and I think this is what people usually mean).

Now that we have a limited number of storage units of size n, are you sure O(n) (not n*log(n)) is the speed? Going through the loop from 1 to n is already n, since you don't have log(n) unit of storage place, you need to go through 1 to n for log(n) times, that give you n*log(n). Of course, you may have a completely different algorithm. In any event, this is a very interesting problem.