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!

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
    2016 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 -> ...)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Merge sort running time O(nlogn) formula
  1. Merging sorted lists (Replies: 0)

  2. Merge sort (Replies: 1)

Loading...