Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 0 down vote accepted
+50

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

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.