What is the largest number of bit operations that can be completed in one second, where each bit operation takes 10^(-9) seconds to complete?

Question

The complete questions reads as follows:

What is the largest n for which one can solve within one second a problem using an algorithm that requires f(n) bit operations, where each bit operation is carried out in 10^(−9) seconds, with these functions f(n)?

I'm stuck trying to find this value for nlog(n). The answer for this problem is provided, but I'm having trouble replicating it.

Given answer: $3.96×10^7$

I'm struggling to get something better than $ \sqrt[\leftroot{-3}\uproot{3}n]{2^{10^{9}}}$. What can I do differently?

Answer 1

We can assume that $f(n)$ is monotonically increasing. So $f^{-1}$ is also monotonically increasing. Therefore, $\sup\{n|f(n)<10^9\}=\sup\{f^{-1}(t)|t<f^{-1}(10^9)\}=f^{-1}(10^9)$.

In the case $f(n)=n\log(n)$, it is difficult to give the explicit expression of $f^{-1}$, but a numerical solution can be found.

Answer 2

You are looking for the $n$ where $n \log{(n)} = 1,000,000,000$.

So you want to solve for $n$ in this equation. Unfortunately, this is not so easy to solve, because there is a special function that is the solution. The Lambert W-function is described in Wikipedia and in Wolfram Mathworld. It's difficult to calculate... Your best bet is to plug in values to get the answer that was given to you.