News for hackers. Stuff that matters.

A comment on Computer Scientists Invent an Efficient New Way to Count. Parent comment

Re:Computer Scientists Invent an Efficient New Way to Count by zero_k on Friday May 17, 2024 @06:37PM (#40394800)
The guarantees would not hold, I'm pretty sure ;) Maybe one of the authors could chip in, but my hunch is that with that you could actually introduce arbitrarily large errors. The beauty of this algorithm really is its simplicity. Of course, simple is.. not always easy. This absolute masterpiece by Knuth should demonstrate this quite well:

https://www.sciencedirect.com/science/article/pii/0022000078...

It's an absolutely trivial algorithm. Its average-case analysis is ridiculously hard. Hence why I think this whole Ordo obsessions needs to be refined -- worst case complexity has often little to do with real-world behavior.

[ Parent | on HN ]
Re:Computer Scientists Invent an Efficient New Way to Count by PeterisP on Saturday May 18, 2024 @04:48AM (#40397452)
Worst case complexity matters when the input data can be manipulated by someone malicious, who can then intentionally engineer the degenerate worst case to happen - as we have seen historically in e.g. denial of service attacks exploiting common hash table implementations with bad worst case complexity.
[ Parent | on HN ]
Re:Computer Scientists Invent an Efficient New Way to Count by Out_of_Characte on Saturday May 18, 2024 @01:10PM (#40400409)
No, you're throwing away a random selection of 50/50. You would have to flood the algorithm with uniques or commons to set the algoritm to a probability of a known state.
[ Parent | on HN ]