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 sortnlgn = nk + nlog(n/k)k = 2 ^ kbut this can never happen and my answer is wrong. how should I solve the problem??Thanks in advance.
the maximum value for which combination of merge sort and insertion sort works more efficiently than standard merge sort?
algorithms;algorithm analysis;time complexity
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)$.