# How to rigorously prove $n = o(k\log k)$ iff $k = \omega \left(\frac{n}{\log n} \right)$

How can one prove that

$$n = o(k\log k)$$

if and only if

$$k = \omega \left( \frac{n}{\log n} \right) .$$

where $k$ and $n$ are functions of the same variable.

Here $o$ represents the small-o notation and $\omega$ represents the small-omega notation. I do not know which way to attack this.

-
Normally $f=o(g)$ means that $f$ and $g$ are functions of the same variable. Are $n$ and $k$ to be considered functions of some unmentioned third variable? – Brian M. Scott Dec 6 '11 at 2:38
sorry for the mix up. n and k are functions of a common variable indeed – Leo Dec 6 '11 at 10:50
Needs more info. for example, "as $n\to \infty$" or something! There is a third variable $t$, maybe "as $t \to 0$" ?? – GEdgar Dec 12 '11 at 20:32
the third variable, say t, goes to infinity and so do n(t) and k(t) – Leo Dec 18 '11 at 17:58

Make the additional assumptions that both $n$ and $k \to +\infty$ (as the common variable goes to some limit). Let $g(x) = x/\log x$. Note that this is increasing for $x \ge e$ and $g(t \log t) = \frac{t \log t}{\log t + \log \log t} < t$ for $t > e$, and $g(t \log t) = t + o(t)$ as $t \to \infty$.

1) Suppose $n = o(k \log k)$. Given $K > 0$, take $\delta = 1/(2 K)$.
For $k$ and $n$ sufficiently large we have $n < \delta k \log k$ so $$k > g(k \log k) > g(n/\delta) = \frac{n}{\delta \log(n/\delta)} > \frac{K n}{\log n}$$ Therefore $k = \omega(n/\log n)$.

2) Conversely, suppose $k = \omega(n/\log n)$. Given $\epsilon > 0$, take $B = 2/\epsilon$. For $k$ and $n$ sufficiently large we have $k > 2 B g(n)$. Now $g(k/B \log (k/B)) = k/B + o(k/B) > g(n)$ , so $n < k/B \log(k/B) < \epsilon k \log k$, for sufficiently large $k$ and $n$. Thus $n = o(k \log k)$

-
Thanks, 1. Could you explain why this last step is true: $$\frac{n}{\delta \log(n/\delta)} > \frac{K n}{\log n}$$ 2. Why did you need: g(tlogt)=t+o(t). you can bound it by t alone. 3. This is a bit hard to read, could you provide some intuition perhaps about the "big picture"? – Leo Dec 17 '11 at 23:10
1. For instance, if $n > 1/\delta^2$, $\log(n/\delta) > \log(n)/2$ 2. I want a lower bound as well as an upper bound. – Robert Israel Dec 19 '11 at 19:11
3. The "big picture" is that $g(x) = x/\log(x)$ is "almost" an inverse function for $f(x) = x \log x$, as $x \to \infty$. – Robert Israel Dec 19 '11 at 19:14

The statement is not true. Suppose e.g. $n = n(k) = 1 + 1/k^2$. As $k \to \infty$ we certainly have $n = o(k \log k)$, but $n/\log n \sim k^2 > k$ so it's not true that $k = \omega(n/\log n)$. You need to make assumptions such as that both $k$ and $n$ (as functions of the common variable) go to $+\infty$.

-