4 ms·
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 examp
by haddr 10y ago
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).
- Jweb_Guru 10y agoUnfortunately, you now have to deal with network transfer between the machines, which are even more expensive than RAM access.
- haddr 10y agoDefinitely 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.
- Jweb_Guru 10y agoThere 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.