Show that \(k \ln k = \Theta(n)\) implies \(k = \Theta(n/ \ln n)\).
Earlier version of this solution proved this using classical definition of \(\Theta\) notation. Which produced a huge wall of text and confused the readers.
As some readers have pointed out in the comment section, it can be (and should be) proved using the symmetry property of the \(\Theta\) notation,
\[k \ln k = \Theta(n) \implies n = \Theta(k \ln k) \tag{1}\]Taking logarithm (base 2) of (1),
\[\ln n = \Theta(\ln (k \ln k)) = \Theta(\ln k + \ln \ln k) = \Theta(\ln k) \tag{2}\]Dividing (1) by (2),
\[\frac n {\ln n} = \frac {\Theta(k \ln k)} {\Theta(\ln k)} = \Theta\left(\frac {k \ln k} {\ln k}\right) = \Theta(k)\]Using symmetry property again,
\[k = \Theta\left(\frac n {\ln n}\right)\]