the maximum value for which combination of merge sort and insertion sort works more efficiently than standard merge sort?

Question

I'm totally new in algorithms and I have a hard time studying how to calculate the time complexity of algorithms.

I'm studying Introduction to Algorithms, by Cormen on my own. Iam doing an exercise and I faced a problem that I couldn't solved it. first, the book asks for the worst time complexity of combination of merge sort and insertion sort. I calculated it truly and the answer is O(nk + nlg(n/k)).

second, it says:

Given that the modified algorithm runs in O(nk + nlg(n/k)) worst-case time, what is the largest value of k as a function of n for which the modified algorithm has the same running time as standard merge sort, in terms of O notation?

this is the part that I have problem. I said the answer may be obtained in this way:

worst time complexity of standard merge sort = worst time complexity of modified merge sort


nlgn = nk + nlog(n/k)
k = 2 ^ k

but this can never happen and my answer is wrong. how should I solve the problem??

Thanks in advance.

Answer 1

Don't forget that big O notation hides constants. We want $nk + n\log(n/k)$ to be at most $Cn\log n$ for some constant $C>0$. This means that $k + \log(n/k) \leq C \log n$, and so $k - \log k \leq (C-1)\log n$. You can check that this inequality holds (for some $C>0$) if and only if $k = O(\log n)$.