Hacker News Reader

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