3
$\begingroup$

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.

  • 0
    the third variable, say t, goes to infinity and so do n(t) and k(t)2011-12-18

2 Answers 2

1

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

  • 0
    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$.2011-12-19
4

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