Given the number $n$. Why does it take maximum of $\frac{n}{\log n}$ digits to represent the number $2^n - 1$ in base of $n$?
Why does it take maximum of $n/\log n$ digits to represent the number $2^n - 1$ in base of $n$?
1
$\begingroup$
elementary-number-theory
computational-complexity
-
0Why is this listed as complex analysis? – 2012-12-13
-
0Because it is a part of a complexity algorithm called Radix-Sort – 2012-12-13
-
1Complexity is not the same as complex analysis, which is analysis on the complex plane. – 2012-12-13
-
0Changed the tag :) – 2012-12-13
1 Answers
0
Hint: to express any number $m$ in base $n$ takes $\lfloor \log_n m \rfloor +1$ digits. To see this, think about base $10$. With one digit you can express any number up to $9$, for which the floor of the log is $0$. With three digits you can express numbers up to $999$, for which the floor is $2$. What base of logs were you planning to use?
-
0Helped a lot! Thanks Ross! – 2012-12-13