1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Merge sort running time O(nlogn) formula

Tags:
  1. Nov 1, 2015 #1
    Hello!
    If T denotes running time, then, as I heard at the lecture,

    T(n/2) + T(n/2) + O(n) = O(nlogn)

    where T(n/2) running time for sorting the left half
    T(n/2) running time for sorting the right half
    O(n) merging sorted

    Please, help me to see the math - how did the left side of expression turned into the right side one?

    Thank you!
     
  2. jcsd
  3. Nov 1, 2015 #2

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    That requires T(n/2) to be O(n logn) and the equal sign is problematic.
    I think the underlying idea is: If you can combine two sets of n/2 elements within O(n) steps, the completely combining n sets of 1 element each to a single set of n elements requires O(n log n) steps because you get log(n) merging steps (lists of 1 -> lists of 2 -> lists of 4 -> ...)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted