Inequality containing logarithms

Question

I've been reading an algorithm book lately. There is this one question that I've been struggling with and can't solve it:

Consider a computer that can do 10^10 operations per second. With an algorithm that has a time complexity of $n *log(n)$. What is the largest input size $n$ that this computer can complete within an hour?

Perhaps this question is pretty simple, but none of the online calculators that I know of (things like symbolab.com) have been able to solve it.

Any help would be greatly appreciated.

Answer 1

You need to solve $n \log(n) = x$ which you can do either iteratively or calling some library functions like ProductLog (see https://mathworld.wolfram.com/LambertW-Function.html). It is not possible to solve it analytically

Answer 2

Hint

$\log (n) = [\log (10) \times \log_{10} (n)] \approx [(2.30) \times \log_{10} (n)].$

Thus, for $n = 10^{k}$,
$n \log(n) \approx [(2.30) \times k \times 10^k].$

Answer 3

$$n \log(n) = x\implies n=\frac{x}{W(x)}$$ where $W(x)$ is Lambert function.

If $x$ is large, you will have a very good approximation using

$$W(x) = L_1 - L_2 + \frac{L_2}{L_1} + \frac{L_2\left(-2 + L_2\right)}{2L_1^2} + \frac{L_2\left(6 - 9L_2 + 2L_2^2\right)}{6L_1^3} +$$ $$\frac{L_2\left(-12 + 36L_2 - 22L_2^2 + 3L_2^3\right)}{12L_1^4} + \cdots $$ where $L_1=\log(x)$ and $L_2=\log(L_1)$.