Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.


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)$. –  WiseBird 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

1 Answer 1

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$


This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .