1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.