4 ms·

The complexity of sorting is done in comparisons. If your system can compare in constant time the complexity is indeed n*log n - if your strings are limited in

The complexity of sorting is done in comparisons. If your system can compare in constant time the complexity is indeed n*log n - if your strings are limited in length there is a constant time upper limit and the complexity holds. Saying that the average length of input strings are log n, seems to be for specific data sets and not a general conclusion. Remember that big-O notation is not about calculating the actual runtimes, but the growths as the input grows. One of the first things you learn in theory is that you must profile this no matter what. Basic complexity theory is not concerned with access times because they work in operations. If your operation involves slow random access over network, then that is the basis. There are branches of complexity theory that takes those exact examples into account. Branches that proves certain time complexity in arbitrary cache hierarchy, or only allow streaming algorithms with no lookback. They all explicitly do this in terms of IO operations. The basic theory is fine, and should be as it is for an introduction. Trying to teach a novice with respect to extremely complex CPUs or broader computer architecture is premature and sure to make many run away screaming. The overarching message should be, and in my experience is, that theory only guides you and profiling is superior.

hinkley 3y ago
> The complexity of sorting is done in comparisons. Yes, and the difference often enough comes down to whether a calculation can be performed in an affordable manner. It may be on demand is not fast enough and a calculation should be done at update time, or in a queue. But it also come down to capacity planning. If you’re off by a factor of logn, it gives a bigger lie to the concept of “economies of scale” (which have always been BS in our field) and you can transition a project from making a healthy profit off of a set of features to going bankrupt on it. Each new customer costing more than you can make off of them until the VC money runs out. Who here hasn’t worked on that project? > Trying to teach a novice with respect to extremely complex CPUs or broader computer architecture I’m not talking about CPU architecture here at all. I’m talking about Information Theory, which they absolutely should be taught, and Physics, which often enough is a requirement for graduation. At least at schools where CS is lumped into the college of engineering. I haven’t sorted integers in about a decade, and maybe three times in two decades. I use BI and telemetry tools that sort them, sure, but that’s someone else’s problem and not part of OLTP workflows. For me it’s a toy problem. Nobody has ever sorted strings in O(nlogn) time. Nobody has ever inserted String->Object mappings into a hash map in O(1) time. Stop lying to intellectuals. They either learn to distrust you or you break them if they don’t.
- mythhabit 3y ago
  > I’m not talking about CPU architecture here at all. I’m talking about Information Theory, which they absolutely should be taught, and Physics, which often enough is a requirement for graduation. At least at schools where CS is lumped into the college of engineering. I would expect any reasonable reputable CS institution to have do this as part of their curriculum. It just is not relevant for the theory of Big-O. If you want to use some of that knowledge in practical applications, then it is relevant, but I expect graduates to be able to make that connection by themself. It is also part of advanced algorithmic theory anyway. > Nobody has ever sorted strings in O(nlogn) time. Nobody has ever inserted String->Object mappings into a hash map in O(1) time. Stop lying to intellectuals. They either learn to distrust you or you break them if they don’t. Big-O is not about "sorting in O(n log n) time", it's about the growth of the algorithm to do so as the input grows. It can obviously only hold as long as the assumptions hold, in this case that comparison is constant time. What that constant is, is of no importance for what you use Big-O for. I'd rather teach intellectuals what Big-O is (upper limit on growth when input size increases), rather than trying to get them to use it for something it isn't (measure runtime as input increases). It's in the very definition of the concept, and at least where I got my degree, it was drilled into our head "it's an upper bound, constants do not matter as the input grows sufficiently".
thewakalix 3y ago
I don't think it's mathematically possible for n distinct strings to have less than O(log n) mean length.
- mythhabit 3y ago
  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.
  - hinkley 3y ago
    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.)
    - mythhabit 3y ago
      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.

hinkley 3y ago

> The complexity of sorting is done in comparisons. Yes, and the difference often enough comes down to whether a calculation can be performed in an affordable manner. It may be on demand is not fast enough and a calculation should be done at update time, or in a queue. But it also come down to capacity planning. If you’re off by a factor of logn, it gives a bigger lie to the concept of “economies of scale” (which have always been BS in our field) and you can transition a project from making a healthy profit off of a set of features to going bankrupt on it. Each new customer costing more than you can make off of them until the VC money runs out. Who here hasn’t worked on that project? > Trying to teach a novice with respect to extremely complex CPUs or broader computer architecture I’m not talking about CPU architecture here at all. I’m talking about Information Theory, which they absolutely should be taught, and Physics, which often enough is a requirement for graduation. At least at schools where CS is lumped into the college of engineering. I haven’t sorted integers in about a decade, and maybe three times in two decades. I use BI and telemetry tools that sort them, sure, but that’s someone else’s problem and not part of OLTP workflows. For me it’s a toy problem. Nobody has ever sorted strings in O(nlogn) time. Nobody has ever inserted String->Object mappings into a hash map in O(1) time. Stop lying to intellectuals. They either learn to distrust you or you break them if they don’t.

mythhabit 3y ago
> I’m not talking about CPU architecture here at all. I’m talking about Information Theory, which they absolutely should be taught, and Physics, which often enough is a requirement for graduation. At least at schools where CS is lumped into the college of engineering. I would expect any reasonable reputable CS institution to have do this as part of their curriculum. It just is not relevant for the theory of Big-O. If you want to use some of that knowledge in practical applications, then it is relevant, but I expect graduates to be able to make that connection by themself. It is also part of advanced algorithmic theory anyway. > Nobody has ever sorted strings in O(nlogn) time. Nobody has ever inserted String->Object mappings into a hash map in O(1) time. Stop lying to intellectuals. They either learn to distrust you or you break them if they don’t. Big-O is not about "sorting in O(n log n) time", it's about the growth of the algorithm to do so as the input grows. It can obviously only hold as long as the assumptions hold, in this case that comparison is constant time. What that constant is, is of no importance for what you use Big-O for. I'd rather teach intellectuals what Big-O is (upper limit on growth when input size increases), rather than trying to get them to use it for something it isn't (measure runtime as input increases). It's in the very definition of the concept, and at least where I got my degree, it was drilled into our head "it's an upper bound, constants do not matter as the input grows sufficiently".

thewakalix 3y ago

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

mythhabit 3y ago
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.
- hinkley 3y ago
  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.)
  - mythhabit 3y ago
    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.