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.