Proof of lower bound for sorting shoes.
From: Smalmatskungen (reply.to_at_group.please)
Date: 10/15/04
- Next message: Smalmatskungen: "Proof of lower bound for sorting shoes."
- Previous message: Smalmatskungen: "Proof of lower bound for sorting shoes."
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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
- Next message: Smalmatskungen: "Proof of lower bound for sorting shoes."
- Previous message: Smalmatskungen: "Proof of lower bound for sorting shoes."
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
