Hacker News Reader

I think that at some point this O(n * sqrt(n)) is actualy not precise. Maybe it works for the first few GB, but then other mechanisms come into play.

For example processing 100GB of data actually don't have to be O(nsqrt(n)) because if you process it on cluster, then other machines are also using L1, L2, L3 caches and RAM. Then the whole process can be streamlined which means that some operations can be faster than the pessimistic nsqrt(n).

View on HN

Unfortunately, you now have to deal with network transfer between the machines, which are even more expensive than RAM access.

Definitely but then is is still n * sqrt(n)? Do I have to add sqrt(n) to each n i'm processing? I doubt so.

I think the problem is that at each stage there is different component (sqrt(n)) that comes into play.

There comes a point where the latency is high enough that you're very unwilling to pay for random access. And very often that point is "broadcast over a network," where think time really is often dominated by things like the speed of light. So yes, it's still n * sqrt(n) in some abstract sense (where n is the amount of theoretically available memory within a given distance over the network); in practice it's much worse than that because you never come close to saturating all the available space between computers with storage nodes.

Reply on news.ycombinator.com