title: Prove running time of optimized mergesort is theta(NK + Nlog(N/K))?
body: <p>Okay, I know Mergesort has a worst case time of theta(NlogN) but its overhead is high and manifests near the bottom of the recursion tree where the merges are made.  Someone proposed that we stop the recursion once the size reaches K and switch to insertion sort at that point.  I need to prove that the running time of this modified recurrence relation is theta(NK + Nlog(N/k))?  I am blanking as to how to approach this problem..</p>