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
    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?2011-12-06
  • 0
    sorry for the mix up. n and k are functions of a common variable indeed2011-12-06
  • 0
    Needs more info. for example, "as $n\to \infty$" or something! There is a third variable $t$, maybe "as $t \to 0$" ??2011-12-12
  • 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
    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"?2011-12-17
  • 0
    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.2011-12-19
  • 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$.