If $m=\omega(N log N)$, then what is the order of $N$ in terms of $m$?

Question

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?

Answer 1

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

Answer 2

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$]

      Contradiction.

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