re: RUM Conjecture - Reasoning About Data Access VIEW POST

re: Usually the metric that is widly used to express the efficency of search, insert and delete operations alongside with space usage is the Big-O nota...

Agreed. The RUM conjecture is more about the trade-off you get when trying to optimize read and write performance + space overhead of a datastructure. Big-O is about asymptotic complexity and can be applied to the RUM overheads. You can express them in Big-O as well, as I am doing in the second post.

I think it's not so much about the actual way to measure the overheads rather than understanding the trade-off that is formulated in the conjecture.

code of conduct - report abuse