Anonymous
Anonymous asked in Computers & InternetProgramming & Design · 6 months ago

# If the time complexity of mergesort is O(n log n) and insertion sort is O(n^2) where n is the input size, how much faster is mergesort?

Relevance
• Asymptotic notation (like big-O or big-theta) for algorithm time complexity doesn't tell you anything about the speed of any particular run. All it tells you is how the algorithm's run time scales with problem size--and it only does that approximately. You can't even use big-O to compare two different implementations of the same algorithm.

What you can say from those two expressions is that if the expected run time of an insertion sort implementation is T for a data set size of n, then doubling the size to 2n will take T' = T * (2n)^2 / n^2 = 4T, running about four times longer.

If a merge sort takes an expected time T to sort n records, then the expected time to sort 2n records is a bit messier:

T' = T * [2n log (2n)] / (n log n) = 2T * log (2n) / log n

= 2T * (log 2 + log n) / log n

= 2T [1 + (log 2)/(log n)]

That's a bit more than twice as long as the sort of n records.

If n is the "crossing point" size where both sorts take the same time T to sort n records, then for sorting 2n records the merge sort will be almost twice as fast as insertion sort.

Both of those assume that n is large enough that the asymptotic behavior dominates the run time. It's also using big-O where big-theta would probably be better. Big-O only specifies

• Login to reply the answers