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: Combinatorics evil problem

  1. Feb 2, 2006 #1
    Combinatorics....evil problem!!

    Hi all,

    I am working on my combinatorics homework. I have completed all of the problems but one. Here it goes:

    ------------------------------------------
    Let S_1 and S_2 be two sets where |S_1| = m and |S_2| = r, for m,r in Z+ (positive integers), and the elements in each of S_1, S_2 are in ascending order. It can be shown that the elements in S_1 and S_2 can be merged into ascending order by making no more than m + r - 1 comparisons. Use this result to establish the following:

    For n >= 0, Let S be a set with |S| = 2^n. Prove that the number of comparisons needed to place the elements of S in ascending order is bounded above by n * 2^n.
    ------------------------------------------

    Please help!!!! Due by 12:00 PM EST tomorrow the 3rd!!
     
  2. jcsd
  3. Feb 2, 2006 #2
    I was able to produce the right result by breaking S into one element sets then combining pairs of them to create half as many sets of two elements and assuming it took the upper bound of m+r-1 comparisons to create each set. I then combined pairs of two element sets to create half as many sets of 4 elements, and so on until I had one set of 2^n elements (S), and summed the upper bounds of all of comparisons required to make each intermediate set and finally S.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook