On the Worst-Case Complexity of TimSort

Re:On the Worst-Case Complexity of TimSort by hinkley on Friday August 31, 2018 @05:58PM (#17888846)

But for instance in a world where horizontal scalability is almost a given, we have to allow that the cost of sending a message between 2 arbitrary servers is going to be at least log(n) time, because if you build a star topology your entire server room would be wires.

So if you're doing a distributed hash, the base cost of fetching two values to compare them is not only nothing to sneeze at, it is probably fundamental to how you solve the problem.

[ Parent | on HN ]

Re:On the Worst-Case Complexity of TimSort by lorenzhs on Saturday September 01, 2018 @08:31AM (#17891539)

Now you’re in some unspecified distributed model without even defining your variables. Again, models are there to allow us to reason about things without going into every detail. It might make more sense to treat the time to open a connection and the time to send one machine word over an established connection as variables in asymptotic analysis. Then you can reason about sequential processing time, communication volume, and latency in one term.

[ Parent | on HN ]