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

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?

• The answer is in pages 27-38 of NG de Bruijn Asymptotic Methods in Analysis NorthHolland – Susan_Math123 Jan 12 '17 at 6:07
• Please let me know if you understand my answer; feel free to ask if you need clarification on the method. – 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}$

• Thanks. Do you mean $N=o(m/log(m))$ is exactly equivalent to $m=\omega(N \log N)$? Is that little o? – Susan_Math123 Jan 11 '17 at 4:03
• The result holds whether you use $o$ or $\Theta$ or just about anything. – marty cohen Jan 11 '17 at 4:05
• 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} )$. – 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)}$.