Solutions for problem 1-1 of Introduction to Algorithms, Third Edition, by CLRS

Question

I'm working problem 1-1 of the textbook Introduction to Algorithms, Third Edition, by CLRS, and need to solve $n\log(n) = 10^6$, where the logarithm is base $2$. My first thought was to use the logarithm laws to get $n \log(n) = \log(n^n) = 10^6 \Rightarrow n^n = 2^{10^6}$, which, as I understand it, is algebraically correct, but doesn't solve for $n$.

This Github page claims that the solution is $6.24 \times 10^4$, but the answers to this Quora question claim that the solution is $8.78 \times 10^4$ (found using numerical methods).

I have reason to doubt the correctness of the Github page, because it also claims that for $\sqrt{n}$ and a time of $1$ hour, we have $1.3 \times 10^{19}$, which I believe is incorrect, since we have $3.6 \times 10^{15}$ for $\sqrt{n}$ and a time of $1$ minute, which, unless I've made an oversight, means that we have $\sqrt{n} = 3.6 \times 60 \times 10^{15} = 2.16 \times 10^{17} \Rightarrow n = 2.16^2 \times 10^{19}$ for $\sqrt{n}$ and a time of $1$ hour.

Is it the Github page that is making errors? Or are the Quora answers incorrect? Or am I also making an error? Or is it some combination?

I would appreciate it if people would please take the time to review this.

Answer 1

You should go the other way, apply the logarithm to the original equation to get $$ \log_2n+\log_2\log_2n=\log_2(10^6)\approx 20 $$ The logarithm of numbers around 20 is between 4 and 5, so that $\log_2n\approx 16\iff n=64\cdot 1024$ appears reasonable. The result of $2^{16}\cdot 16=2^{20}=(1024)^2$ is slightly larger than the target value, further refinements need a numerical algorithm or the Lambert-W function.

As a first correction, notice that the function value is about $5\%$ too large. Reduce $n$ by the same percentage ($1024$ to $1000$ are $2.5\%$, the remaining $2.5\%$ give $64-1.6$) to get $n=62.4\cdot 10^3$ as second guess. The exact solution is $62746.126...$, in the spirit of the task you have to round down for the correct answer.

Answer 2

The Quora answer is correct but it is using natural logs not logs to the base 2.

I think you must be misunderstanding the Github page. For example, consider the $\sqrt{n}$ function.

$1$ hour is $3600 \times 10^6$ microseconds. Let $\sqrt{n}=3600 \times 10^6$ and you obtain $n=3600^2\times 10^{12}=1.296\times 10^{19}$ as (approximately) stated. Similarly the log to the base 2 answer is (approximately) correct although $6.27\times 10^4$ is more accurate.

Answer 3

As noted in Lutz's answer, we have

$$\log_2(n)+\log_2(\log_2(n))=6\log_2(10)\simeq6\cdot\frac{10}3=20$$

Let $x=\log_2(n)$ to reduce the size of what we're working with to get

$$x+\log_2(x)=6\log_2(10)\simeq20$$

It is easy to observe that $16+\log_2(16)=20$. By applying fixed-point iteration for

$$x=6\log_2(10)-\log_2(x)$$

we get in only 4 steps the result of

$$x\simeq\color{#2288FF}{15.9372}42985748778$$

$$n\simeq\color{#2288FF}{62746}.309434432704$$