Proof of lower bound for sorting shoes.

From: Smalmatskungen (reply.to_at_group.please)
Date: 10/15/04 

Date: Fri, 15 Oct 2004 22:54:20 +0200

n left shoes and n right shoes has to find it's owner among n people.
I fail to see why a decision tree with three edges (>, =, <) for each node
will contain n! * n! leaves in this case.
Anyone willing to give a short explanation why this is so?
The fact that the height with this number of leaves is O(n*log n) is clear
to me BTW, so I'm just confused about the amount of leaves.

/Nic

Relevant Pages

  • Proof of lower bound for sorting shoes
    ... n left shoes and n right shoes has to find it's owner among n people. ... I fail to see why a decision tree with three edges for each node ...
    (comp.programming)
  • Proof of lower bound for sorting shoes
    ... n left shoes and n right shoes has to find it's owner among n people. ... I fail to see why a decision tree with three edges for each node ...
    (comp.programming)
  • Proof of lower bound for sorting shoes
    ... n left shoes and n right shoes has to find it's owner among n people. ... I fail to see why a decision tree with three edges for each node ...
    (comp.programming)
  • Proof of lower bound for sorting shoes.
    ... n left shoes and n right shoes has to find it's owner among n people. ... I fail to see why a decision tree with three edges for each node ...
    (comp.theory)
  • Proof of lower bound for sorting shoes.
    ... n left shoes and n right shoes has to find it's owner among n people. ... I fail to see why a decision tree with three edges for each node ...
    (comp.theory)