World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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

###### Answered By : Yuval Filmus

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.

Question Source : http://cs.stackexchange.com/questions/65486

3200 people like this