> This square of N notation falls apart in other cases. Not particularly; since O(n^1/2) is typically used as a catchall for all O(n^x) where 0 < x < 1. The wh

> This square of N notation falls apart in other cases. Not particularly; since O(n^1/2) is typically used as a catchall for all O(n^x) where 0 < x < 1. The whole idea of Big O notation is that it provides an idea of systemic complexity that is normalized to a theoretical "constant" system represented by a coefficient (that is usually dropped when writing out the Big O). IMO it still holds: distributed systems behave differently than local ones. Now that we're writing algorithms on the cloud, we've added an abstraction layer that adds complexity, and that brings some non-constant amount of overhead. It didn't make sense to think about memory like this 50 years ago; but it does now.