Timeline for Searching the symmetric group
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 21, 2009 at 21:33 | comment | added | David E Speyer | Oh, good point. No, I don't think it can. If there are ever two elements, i and j, which are not directly compared, then we can't distinguish the permutations ij... and ji... , where the ellipsis are the same permutation in both cases. So we need (n choose 2) comparisons. | |
| Dec 21, 2009 at 18:38 | comment | added | Greg Kuperberg | David, can a sorting network be made non-adaptive in the same sense as Gabe's questions? In other words, in the sense of determining a permutation "with 20 questions" with the questions set in advance. I would think that it isn't the same model. | |
| Dec 21, 2009 at 16:55 | comment | added | David E Speyer | You can sort n elements in O(log_2 n!) time even if later comparisons are not allowed to depend on earlier ones. See doi.acm.org/10.1145/800061.808726 I don't know whether the best constant in the O( ) is known. | |
| Dec 21, 2009 at 16:24 | history | answered | Michael Lugo | CC BY-SA 2.5 |