title: If klgk = Θ(n), then k = Θ(n/lgn)
body: <p>Ok so first off I'm new to this site so if by some chance I'm doing anything wrong please let me know.  I need help with the following proof.  I am NOT looking for the answer, simply guidance.</p>
  
  <p>Using the definition of Θ, prove the following:
  If klgk = Θ(n), then k = Θ(n/lgn).</p>
  
  <p>My professor told us to start with k &lt; n.  Then take the log of both sides, giving us lg(k) &lt; lg(n).  Then multiply both sides by k, finally giving us k*lgk &lt; k*lgn.  From here we can say k*lgn &lt;= c2*n, and dividing both sides by lgn, we have k &lt;= c2 * (n/lgn).  Thus k = O(n/lgn).  Why is it that in the beginning we can say that k &lt; n?  Am I missing something?  Thanks in advance for any help.</p>