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?

1 Answer

  • 6 months ago

    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
Still have questions? Get your answers by asking now.