Hacker News new | past | comments | ask | show | jobs | submit login

Or stated equivalently: The only operations allowed on elements are binary comparisons and two-element swaps, but both are O(1).



Kiiinda. Two-element swaps are a stretch already for merge sort, especially the O(log N)-space linked list version, let alone search trees and so on. At some point you also need to make sure you can’t sneak arbitrary computation into the (necessarily unlimited-magnitude) array index.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: