proving " if $k\log(k) = \theta (n)$ then $k = \theta (\frac{n}{\log(n)})$"

Question

First i began with the definition of $\theta$ as below: $c_1n \leq k \log(k) \leq c_2n \implies c_1\frac{n}{logk} \leq k \leq c_2\frac{n}{logk}$ and we also know if $k\log(k) = \theta (n)$ then $k = O(n)$ then $k \leq cn$ thus $c\frac{n}{logn} \leq c_1\frac{n}{logk}\leq k $ and thus $k = \omega(\frac{n}{\log(n)})$. In in this manner, i have to prove that $ c_2\frac{n}{logk} \leq c\frac{n}{logn}$ too to show that $k = O(\frac{n}{\log(n)})$ . But it ($ c_2\frac{n}{logk} \leq c\frac{n}{logn}$) seems false! Is this really false and there is a better solution, or is there any proving tricks for $ c\frac{n}{logn} \leq c_1\frac{n}{logk}$?

Answer 1

First, let me explain why your claim holds. Then we'll see how to prove it.

If $k \log k = \Theta(n)$ then $k$ has the same order of magnitude as $n$, and so we expect $\log k \approx \log n$ (or, more formally, $\log k = \Theta(\log n)$). Diving by $\log n$, we deduce $k = \Theta(n/\log n)$.

This was just intuition, so now let us see a rigorous proof. A rigorous proof rests on a rigorous definition of big $\Theta$, and this is a surprisingly delicate matter. In this case it suffices to assume that $n \geq 1$.

Upper bound

Suppose that $k \log k \leq Cn$ for $C>0$.

If $k \leq \sqrt{n}$ then $$ \frac{k}{\frac{n}{\log n}} \leq \frac{\log n}{\sqrt{n}}. $$ Now $\frac{\log n}{\sqrt{n}}$ is continuous and tends to zero at infinity, so it is upper-bounded by some constant $M$. Therefore in this case $$ k \leq M \frac{n}{\log n}. $$

If $k > \sqrt{n}$ then $$ Cn \geq k \log k > k \log \sqrt{n} = \frac{1}{2} k \log n, $$ and so $$ k \leq 2C \frac{n}{\log n}. $$

We conclude that for all $k$, $$ k \leq \max(2C,M) \frac{n}{\log n}. $$

Lower bound

Left to you as an exercise.