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
which can be helpful.
Thanks.
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
which can be helpful.
Thanks.
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$