2.1.c

[FXTY]

Θ(nk+nlg(n/k))
=Θ(nk+nlgn−nlgk)
=Θ(nlgn+nlgn−nlg(lgn))
=Θ(2nlgn−nlg(lgn))
=Θ(nlgn).

Why is the penultimate line of the equation equal to the last line of the equation, should it be approximately equal here?

This error seems obvious, assuming n is equal to 16, the second-to-last line of the equation has a value of 128, and the last line of the equation results in 32. If only the highest order item is taken, then the second line of the equation should be directly equal to the last line.

The question here is what is the minimum value of k, here you seem to be directly making an assumption, why do you assume that, and what is the basis for the assumption?

​

[leverimmy]

From my point of view, the essence lies in solving the equation $$\Theta(nk + n\lg n - n\lg k) = \Theta(n\lg n).$$
By crossing out the irrelevant $n\lg n$ term on the left side, what we really need to solve is $$\Theta(n(k - \lg k)) = \Theta(n\lg n).$$

It is quite intuitive to say that we can also cross out the factor $n$ on both sides, which leads to $\Theta(k - \lg k) = \Theta(\lg n)$. Treat the left side as a function of $k$ instead of $n$, then directly we omit the $\lg k$ term and obtain that $k = \Theta(\lg n)$.