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.

Thanks.

share
2  
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$

share

This site is currently not accepting new answers.

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