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