$k\ ln\ k = \Theta (n)$ implies there exists constants $c_1, c_2, n_0 >0$ such that ∀$n>n_0$, $c_1n<k\ ln\ k <c_2n$.
Assuming that $n_0>e$, $ln\ n>1$.
So, $\frac{c_1n}{ln\ n} \leq k\frac{ln\ k}{ln\ n} \leq \frac{c_2n}{ln\ n}$
Taking log of all terms, we get: $ln(c_1n)\leq ln(k\ ln\ k)\leq ln(c_2n)$
If $k$ is large enough we can safely write, $ln\ k + ln(ln\ k)< 2 ln\ k$ and also $ln\ k + ln(ln\ k)> ln\ k$.
∴$ln(c_1)+ln\ n<2\ ln\ k$
Dividing the above equation by $2\ ln\ n$, we get:
$\frac{ln\ c_1}{2\ ln\ n} + \frac{1}{2}<\frac{ln\ k}{ln\ n} \Rightarrow k \frac{ln\ k}{ln\ n}>\frac{1}{2}k$
Similarly, we can upper bound the term $k \frac{ln\ k}{ln\ n}$ as: $ln\ k < ln(c_2)+ln\ n$ [because $ln\ k + ln(ln\ k)> ln\ k$.]
This means, $\frac{ln\ k}{ln\ n}<\frac{ln(c_2)}{ln\ n}+1$
Choosing $c_2$ in such a way that $ln(c2)\leq1$ will ensure that $\frac{ln\ k}{ln\ n}<2$ or $\frac{ln\ k}{ln\ n}<2 \Rightarrow k\frac{ln\ k}{ln\ n}<2k$
Thus we have bounded the term $k\frac{ln\ k}{ln\ n}$ as:
$\frac{1}{2}k<k\frac{ln\ k}{ln\ n}\leq \frac{c_2n}{ln\ n}$ and $2k>k\frac{ln\ k}{ln\ n}\geq\frac{c_1n}{ln\ n}$
Now it is easy to find bounds on $k$.
We get $k<2c_2.\frac{n}{ln\ n}$ and $k>\frac{c_1}{2}.\frac{n}{ln\ n}$
In other words, $\frac{c_1}{2}.\frac{n}{ln\ n}<k<2c_2.\frac{n}{ln\ n}$
Hence the answer follows: $k=\Theta(\frac{n}{ln\ n})$
