1
$\begingroup$

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.

What I've tried

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Mar 25, 2020 at 10:11
  • $\begingroup$ @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 ... $\endgroup$
    – akuzminykh
    Commented Mar 25, 2020 at 11:00
  • $\begingroup$ "Iterative Method". $\endgroup$
    – gnasher729
    Commented Mar 25, 2020 at 14:22
  • 1
    $\begingroup$ 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. $\endgroup$
    – Laakeri
    Commented Mar 25, 2020 at 14:42
  • $\begingroup$ Asked on Mathematics: math.stackexchange.com/questions/1301343/… (this is different than the question you link to). $\endgroup$ Commented Mar 25, 2020 at 16:20

2 Answers 2

3
$\begingroup$

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.

The Lambert W functions is implemented in any popular mathematical software. It can be evaluated using standard techniques such as Newton's method or its second derivative generalization, Halley's method; see the Wikipedia article (under Numerical Evaluation).

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

$\endgroup$
2
  • $\begingroup$ Did you mean $x = e^{\log n} \log n$ ? $\endgroup$
    – Steven
    Commented Mar 25, 2020 at 16:59
  • $\begingroup$ Thanks! There were also a few other mistakes. $\endgroup$ Commented Mar 25, 2020 at 17:32
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – akuzminykh
    Commented Mar 25, 2020 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.