Hacker News Reader

Comment by thewakalix | Hacker News Reader

I don't think it's mathematically possible for n distinct strings to have less than O(log n) mean length.

You're right. I missed that crucial word, and the argument still stands, as long as you have an upper bound of the length of the strings, you can do comparisons in constant time.

And that’s my point. There is no upper bound on the length of strings. If your data continues to grow it is because the information inside of it is distinct in some way. Nobody is putting “a” into an ordered list or into a set billions of times. They’re putting John Smith at 123 Sesame St, Springfield, MO into that list.

If we had a billion Americans, we’d have to use 9 digit zip codes to distinguish customers. The data grows logarithmically. Always.

This is less true in event processing, but groups of events are often information in that case, so the pattern still mostly holds. (Maybe someone could convince me that events are loglogn, but we also deal with 3 orders of magnitude more of them than any other data at my job.)

Not all data entries in every dataset is distinct, far from it. It seems to me, that you are trying to argue that big O is not useful, because you believe that an assumption of constant time comparison cannot be done. But I disagree, once we go into the realm where we cannot assume that comparisons are constant time, we are also in the realm where IO operations dominate the runtime, and we base our big O on IO operations rather comparisons. Here the bound and big O is even more relevant.

Reply on news.ycombinator.com