On: Designing far memory data structures: think outsid...

[amelius]

Shouldn't we use better notation for the time complexity of the algorithms? For example, an algorithm can have

    O(n^2) + rt * O(n)

time complexity (where rt is the round trip time). Of course this expression collapses to O(n^2), but by writing it like above you can more clearly see where the cost comes from.

EDIT: on second thought, perhaps bring the rt under the O() together with n.

[sagebird → amelius]

I agree with the spirit, but why use O here at all? Isn’t the idea that O collapses to its highest ordered term, so if you don’t want that, don’t use it.

You could use a normal function. Like t(n) = f(n^2) + g(n) + rt

[afiori → sagebird]

The point is that all the nice manipulation you would like to do are sound in O-notation and unsound in many other notations, what the parent wants is

O(n^2) + O(m) * O(n)

where m is the number of roundtrips.

[sterkekoffie → afiori]

Writing an O in front of something doesn't mean it's in big O.

[afiori → sterkekoffie]

You can use every tool in the wrong way; if you stay in simple cases it is (comparatively) hard to misuse big-O notation.