1

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.

Michael Hardy
  • 1
Sergey Sokolov
  • 157
  • 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 05 '12 at 17:11
  • Are you sure? Because if $k$ is function of $n$ then it should be $k(n)$. – Sergey Sokolov Aug 05 '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 05 '12 at 17:56

2 Answers2

4

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$

rusty
  • 56
  • 1
0

$$c_1n \leq klnk \leq c_2n$$ $$ln(c_1n) \leq ln(klnk) \leq ln(c_2n) \\ln c_1 + ln n \leq lnk + lnlnk \leq lnc_2 + ln n\\ \frac{1}{2}ln n \leq ln n + lnlnk \leq 2lnn\\ \therefore lnk +lnlnk = \Theta(ln n)\\ and\\ lnk \leq lnk+ ln lnk \leq 2lnk\\ \therefore ln k + lnlnk \Theta(ln k)\\ reflexivity \implies\\ ln k = \Theta(lnk+ lnlnk)\\ transitivity \implies\\ lnk = \Theta(lnn)\\ $$ $$c_1n \leq klnk\\ c_2lnn \geq ln k\\ \frac{c_1n}{c_2lnn} \leq k$$

Daniel Kunkler
  • 33