Assume $m=\omega(N \log N)$. What is the order of $N$ in terms of $m$?

My answer: I found that if $N=m^{1-a}$ where $0<a<1$, then $m=\omega(N \log N)$ holds. But, I think this is not a good representation.

Then I thought of Lambert $W$ function. I think we can say $\log{N}=o(W(m))$ thus $N=o(e^{W(m)})$. But, I need more simplification. I should know the asymptotic behavior of $W(m)$ as $m \to \infty$. Any idea?

  • $\begingroup$ The answer is in pages 27-38 of NG de Bruijn Asymptotic Methods in Analysis NorthHolland $\endgroup$ – Susan_Math123 Jan 12 '17 at 6:07
  • $\begingroup$ Please let me know if you understand my answer; feel free to ask if you need clarification on the method. $\endgroup$ – user21820 Jan 24 '17 at 7:29

$N$ is of order $\dfrac{m}{\log m}$.

To see this,

$\begin{array}\\ N \log N &=\dfrac{m}{\log m} \log(\dfrac{m}{\log m})\\ &=\dfrac{m}{\log m} (\log(m)-\log \log m))\\ &=m-\dfrac{m\log \log m}{\log m}\\ &=m(1-\dfrac{\log \log m}{\log m})\\ &=m(1-o(1))\\ \end{array} $

  • $\begingroup$ Thanks. Do you mean $N=o(m/log(m))$ is exactly equivalent to $m=\omega(N \log N)$? Is that little o? $\endgroup$ – Susan_Math123 Jan 11 '17 at 4:03
  • 2
    $\begingroup$ The result holds whether you use $o$ or $\Theta$ or just about anything. $\endgroup$ – marty cohen Jan 11 '17 at 4:05
  • $\begingroup$ Thanks. But you have shown that $N=o(m/\log {m} )$ results $N log{ N} = o(m)$. This is just one side. It is not proved that $N log{ N} = o(m)$ yields $N=o(m/\log {m} )$. $\endgroup$ – Susan_Math123 Jan 11 '17 at 4:10

Take any variables $m,N \ge 0$ such that $m \in ω(N \log(N))$ as $N \to \infty$. $ \def\lfrac#1#2{{\large\frac{#1}{#2}}} $

Given any constant $c > 0$:

  As $m \to \infty$:

    If $N > c \cdot \lfrac{m}{\log(m)}$:

      $N \to \infty$.

      $m \ge \lfrac2c \cdot N \log(N) > 2 \lfrac{m}{\log(m)} ( \log(m) - \log\log(m) + \log(c)) > m$.

        [since $2 \log(m) > \log\log(m)$ as $m \to \infty$]


    Therefore $N \le c \cdot \lfrac{m}{\log(m)}$.

Therefore $N \in o(\lfrac{m}{\log(m)})$ as $m \to \infty$.

If it is not clear why the above proof is valid, you can translate it as follows. If there is a sequence of points for which $m \to \infty$ but $N > c \cdot \lfrac{m}{\log(m)}$, then $N \to \infty$ for that sequence, and we will get a contradiction in exactly the same way. Therefore given any sequence of points for which $m \to \infty$, eventually $N \le c \cdot \lfrac{m}{\log(m)}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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