Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is exercise (3.2-8) from Introduction to Algorithms book. I need help to solve it.

I am confused by the fact that there are two parameters. Because usually one parameter is used. There is related exercise

enter image description here
which can be helpful.


share|cite|improve this question
The question in the title is not related to that exercise: here there is only one parameter $n$, and $k$ is supposed to depend on $n$. – Robert Israel Aug 5 '12 at 17:11
Are you sure? Because if $k$ is function of $n$ then it should be $k(n)$. – Sergey Sokolov Aug 5 '12 at 17:45
If $k$ is not a function of $n$ then $k\ln k$ is a constant with respect to $n$, and thus necessarily in $\Theta(n)$; then it wouldn't make any sense to say something about what this "implies". – joriki Aug 5 '12 at 17:56
up vote 2 down vote accepted

I wouldn't call this rigorous, but here's an idea:

If $f \in\Theta(g)$, say $f \sim g$.

So we have $n \sim k\ln k$ and want to show $n/\ln n \sim k$. Well if $n \sim k\ln k$, then $\ln n \sim \ln (k \ln k) \sim \ln k + \ln \ln k \sim \ln k$.
Note: this requires rigorous justification, and I'm not exactly sure it's right

So $n/ \ln n \sim k \ln k / \ln k \sim k$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.