How to find the inverse of $n\log n$? 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.
 A: 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.
A: 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$$
A: So I was provided 2 possible solutions by some friends:

*

*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$.


*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.
