Timeline for Binary search generalizations for posets?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 11, 2011 at 18:07 | comment | added | Suresh Venkat | Not sure yet. thinking out loud. But it's an excellent question. | |
| Nov 11, 2011 at 18:05 | comment | added | jkff | In a sense yes, but that's far from being the complete answer — eg it doesn't give bisection for the 1d or 2d cases :) what do you suggest to do with the roots? | |
| Nov 11, 2011 at 16:20 | comment | added | Suresh Venkat | I see. So actually in your case you'd like a decomposition into the ideals and then examine the roots | |
| Nov 11, 2011 at 15:08 | comment | added | jkff | Well - I'm talking about the complexity in terms of the number of evaluations of predicate P, not the comparison predicate. | |
| Nov 11, 2011 at 14:29 | comment | added | Suresh Venkat | But that's the point. Without data structures you can't get log n even for s totally ordered set, because all you can do is scan. It's actually a really nice question to try and find a BST equivalent. | |
| Nov 11, 2011 at 5:46 | comment | added | jkff | Heh, sounds not too inspiring compared to log(n) :) but thanks anyways! | |
| Nov 11, 2011 at 4:58 | history | answered | Suresh Venkat | CC BY-SA 3.0 |