# Solving equation with $n\log n$

Given a computer that takes 1 microsecond for an operation, I'm trying to find the amount of operations this computer can perform in one second, given an algorithm with complexity $$O(n\log n)$$. I've tried to solve it by the following ways but always get stuck. Note that one second equals $$10^6$$ microseconds.

I've found this post where it's stated that "there is no simple way" to solve that but I still want to ask here if there is any different approach to the question from a "computer science perspective".

• There's no "computer science perspective", this is Numerical Mathematics for beginners. n = 10^6 / log n. Set n = 1,000,000. Evaluate the right side. Set n to the result. Evaluate the right side and repeat until the result doesn't change. Commented Mar 25, 2020 at 10:11
• @gnasher729 Thank you! This works well for me. May I ask what the name of this method is? I'd like to study that and this seems like a good starting point ... Commented Mar 25, 2020 at 11:00
• "Iterative Method". Commented Mar 25, 2020 at 14:22
• If the complexity is $O(n \log n)$, you cannot know how many operations it will take on a computer. The underlying constant of O-notation could be 1000000 or 0.00001. Commented Mar 25, 2020 at 14:42
• Asked on Mathematics: math.stackexchange.com/questions/1301343/… (this is different than the question you link to). Commented Mar 25, 2020 at 16:20

If $$n\log n = x$$ then $$x = e^{\log n} \log n$$ and so $$\log n = W(x)$$, where $$W$$ is the Lambert $$W$$ function.
Roughly speaking, $$n = e^{W(x)} \approx e^{\log x - \log\log x} = x/\log x$$. The Wikipedia article contains concrete bounds (under Asymptotic expansions).
• Did you mean $x = e^{\log n} \log n$ ? Commented Mar 25, 2020 at 16:59
No way to say. $$T(n) = O(n \log n)$$ means there exist constants $$c > 0, N_0$$ so that for all $$n \ge N_0$$ it is $$T(n) \le c n \log n$$. They are anything, i.e., it might be valid only for ridiculously large $$n$$ (large $$N_0$$), or even for small $$N_0$$, like $$N_0 = 10$$, the constant $$c$$ could be such that all you know is that $$T(100) \le \text{one milisecond}$$ or $$T(100) \le \text{one week}$$.
• I'm sorry for not being precise in my question text. The function/algorithm I'm talking about is $f(n) = nlog_2n$, thus the equation I'm trying to solve is $nlog_2n = 10^6$ where the $10^6$ is the amount of microseconds in a second. As stated in the question, we asume a computer that takes 1 microsecond for 1 operation. The $O(nlogn)$ is just a side note, the important thing is in the picture. Commented Mar 25, 2020 at 18:19