Show that \(k \ln k = \Theta(n) \implies k = \Theta \left( \frac{n}{\ln n} \right)\).

Via symmetry, we have \(f(n) = \Theta(g(n)) \iff g(n) = \Theta(f(n))\) so \(k \ln k = \Theta(n) \implies n = \Theta(k \ln k)\).

\[\begin{equation} \begin{split} \ln n & = \Theta ( \ln ( k \ln k)) \\ & = \Theta( \ln k + \ln \ln k) \\ & = \Theta ( \ln k) \end{split} \end{equation}\]

Since we now have the values of both \(\Theta(n)\) and \(\Theta(\ln n)\) which via symmetry give us \(n\) and \(\ln n\):

\[\begin{equation} \begin{split} \frac{n}{\ln n} & = \frac{\Theta(k \ln k)}{\Theta ( \ln k)} \\ & = \Theta \left( \frac{k \ln k}{\ln k} \right) \\ & = \Theta(k) \end{split} \end{equation}\]

Therefore with the help of symmetry one last time, we conclude that \(k = \Theta \left( \frac{n}{\ln n} \right)\).