[Solved]: Why is the unary representation of a number exponentially larger than a base k representation of it?

Problem Detail: 

According to a book I am reading, the unary representation of a number exponentially larger than a base k representation of it. I, however, feel that the unary representation should scale linearly with the input.

After all, 1 is 1, 2 is 11, 3 is 111, and so on, right? Wouldn't that be linear?

Asked By : John Hoffman

Answered By : Luke Mathieson

The base $k$ representation of the number $n$ takes $\log_{k}n$ bits, whereas the unary representation takes $n$, and of course $n = k^{\log_{k}n}$

The gap is more apparent with larger numbers, if we take our normal base 10 system, then writing 1000 takes 4 decimal digits, but writing it in unary takes 1000 ones.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7062