1
$\begingroup$

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}$?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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