How to find the inverse of $n\log n$?

Question

So I'm on chapter $1$ of introduction to algorithms & at the end the book proposes a problem: here

The answers are there & I was able to work through most of them myself despite my lack of math skills by finding the inverse of the $f(n)$'s in the leftmost column. For instance, the $n^3$ has an inverse of $\sqrt[3]{n}$ but what is the inverse for $n \log_2 n$?

However, there is $n\log_2n = 1000000$ microseconds which I cannot figure out how to find the inverse of ($n = 62746$). I'm writing python code so that way I don't screw up my calculations as I move through the table but I have no idea how to find this.

I'm not very math savvy so if you use notation, can you please name it so I can google it?

If it's not possible to reverse engineer - can someone please explain how was $62746$ calculated for that row/column combination?

Thank you for your help.

Answer 1

Newton's Method http://en.wikipedia.org/wiki/Newton%27s_method is effective. To solve $f(x)=N$, start with a rough estimate, $x=a_0$, of the solution.
Then replace that estimate with $a_1=a_0-(f(a_0)-N)/f'(a_0))$, where $f'(x)$ is the derivative of $f(x)$. In this case, $f(x)=x\log_2x$, so $f'(x)=\log_2x+(1/\ln2)$.
A rough guess for the answer is $$a_0=\frac{N}{\log_2 N}$$
For your example, $$a_0=1000000/\log_21000000\approx50000\\ a_1=a_0-\frac{a_0\log_2 a_0-1000000}{(1/\ln2)+\log_2 a_0}=62873\\ a_2=a_1-\frac{a_1\log_2 a_1-1000000}{(1/\ln2)+\log_2 a_1}=62746$$

Answer 2

So I was provided 2 possible solutions by some friends:

1. Use binary search (brute force) to find the number which exceeds $t$ (the column value from the table) in microseconds, so iterate over numbers from 1-t and stop when I find a $n$ whose output from $f(n)$ exceeds or equals $t$ and take the previous $n$.

2. Use the lambert function as follows $e^{W(t*log(2))}$ where $t$ is the column value in the table.

   Thank you guys for all of your feedback, I learned more from researching the stuff you shared with me.

Answer 3

There's a fairly easy way to numerically solve $n \log_2 n = t$, using the fact that $n$ and $t$ are not too far apart and especially their logs are close together. Just write this as $n = \frac{t}{\log_2 n}$ and then do a fixed point iteration, starting with say $n_0=t$.

\begin{align} n_0 &= 1000000 \\ n_1 &= \frac{1000000}{\log_2 n_0} \approx 50172 \\ n_2 &= \frac{1000000}{\log_2 n_1} \approx 64043 \\ n_3 &= \frac{1000000}{\log_2 n_2} \approx 62630 \\ n_4 &= \frac{1000000}{\log_2 n_3} \approx 62756 \\ n_5 &= \frac{1000000}{\log_2 n_4} \approx 62745 \\ n_6 &= \frac{1000000}{\log_2 n_5} \approx 62746 \\ \end{align}

Essentially this works because $\log_2 n$ is very contractive (for large values of $n$), so the relative error of $\log_2 n$ (compared to the exact value) is smaller than the relative error of $n$. Convergence is not as rapid as a proper Newton iteration as in Michael's answer, but it is terribly simple and, for large values of $t$ measurably faster than binary search.