Well, this is a mathematical minimization problem, and to solve it, we
need some basic calculus.
We need to find the value of
k for which
n*lg(n/k)] / dk == 0.
We should also check for the edge cases, which are
k == n,
k == 1.
The candidate for the value of
k that will give the minimal
n*k + n*lg(n/k) is the minimum in the required
range, and is thus the optimal value of
Attachment, solving the derivitives equation:
d[n*k + n*lg(n/k)] / dk = d[n*k + nlg(n) - nlg(k)] / dk
= n + 0 - n*1/k = n - n/k
n - n/k = 0 => n = n/k => 1/k = 1 => k = 1
Now, we have the candidates: k=n, k=1. For k=n we get
O(n^2), thus we conclude optimal
Note that we found the derivitives on the function from the big Theta,
and not on the exact complexity function that uses the needed constants.
Doing this on the exact complexity function, with all the constants
might yield a bit different end result - but the way to solve it is pretty
much the same, only take derivitives from a different function.