Tell me more ×
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.
up vote 0 down vote favorite

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|improve this question
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

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|improve this answer

Your Answer

 
discard

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.