1. Not finding help here? Sign up for a free 30min 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!

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

Have something to add?

Similar Discussions: Combinatorics evil problem
  1. Combinatorics problem (Replies: 7)

  2. Combinatorics problem (Replies: 7)

  3. Combinatorics problem (Replies: 2)

  4. Combinatorics problems (Replies: 8)