Hacker News Reader

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.

> 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.

> 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".

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.

Knuth isn't wrong, he is taken out of context. Knuth doesn't say programmers shouldn't worry about performance. You still have to define in the problem and the requirements and fulfill those reqs.

> There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3 %. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools for seven years, I've become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off.

He says we need better tooling that continuously tells us which parts of the program are taking the most time and why. Yes! We do need this.

page 268, https://dl.acm.org/doi/10.1145/356635.356640 Structured Programming with go to Statements

I’m not talking about the “premature optimization” conversation for once. I’m talking about complexity theory, which he is the father of, being unmoored from information theory and problematic in this day and age - actually problematic back to 2000 if you’re working on problems that require clusters of machines. In the last 20 years we’ve flipped from less than 20% of developer working in horizontally scaled systems to perhaps 20% who have never had to. I believe that accentuated the discrepancy.

> Complexity theory tells us you can sort those in nlogn time.

You seem to be attacking a strawman — no CS textbook says you can sort n strings in O(n log n) time (that's just the number of comparisons); of course sorting n strings each of length m will take O(mn log n) time — that is, you have to multiply by the average time for each comparison. This is what complexity theory says, and what any good textbook would also say. You don't need "a new complexity theory built on top of Information Theory"; the current one already does so. (And m could be much bigger than log n too.)

I’ve seen actual implementations of hash tables claim O(1) amortized insertion time, not O(m). And I misspent a summer about 5 years back thinking I had a constant space overhead mergesort (when what I had was poorly chosen input data. Bummer). I read a lot of mergesort papers then. Nobody mentioned m. I may get bored and check your theory on textbooks, but I suspect you’re letting optimism get the better of you. In a conversation about pragmatism that’s not good.

All of my examples at the top were not hypothetical, they were all actual arguments I’ve had with real people or documentation I bitched to someone about.

Edit: I mean fuck, even Wikipedia has it wrong:

> In sorting n objects, merge sort has an average and worst-case performance of O(n log n).

N objects. Not n numbers. If you want to fix the world instead of declaring bankruptcy with me, start there.

At least they get space overhead right farther down:

> In this case, the notion of "in-place" can be relaxed to mean "taking logarithmic stack space", because standard merge sort requires that amount of space for its own stack usage.

Well, Wikipedia is obviously wrong there. I've fixed it to say number of comparison operations: https://en.wikipedia.org/w/index.php?title=Merge_sort&diff=p...

Note also that in computational complexity theory, "n" is the length of the input in bits: if you have k strings each of length l, using a regular sort, with a comparison subroutine that takes O(l) time, will take O(kl log k) time — O(k log k) operations each taking O(l) time — which, as n=kl, is O(n log k), upper-bounded by O(n log n).

————

I looked up a couple of influential algorithms textbooks in the meantime, and I must admit this is less clear than I'd have liked (though complexity theorists are very aware of it).

• TAOCP vol 3 (which starts with Chapter 5, Sorting) says, on page 5 (in the introduction section of the chapter, where he often says things informally and not exactly):

> The time required to sort N records, using a decent general-purpose sorting algorithm, is roughly proportional to NlogN; we make about logN “passes” over the data. This is the minimum possible time, as we shall see in Section 5.3.1, if the records are in random order and if sorting is done by pairwise comparisons of keys. Thus if we double the number of records, it will take a little more than twice as long to sort them, all other things being equal. (Actually, as N approaches infinity, a better indication of the time needed to sort is N(logN)^2, if the keys are distinct, since the size of the keys must grow at least as fast as logN; but for practical purposes, N never really approaches infinity.)

It's emphasized less than I'd have liked but he has already mentioned your observation though (and I checked this was present in the first edition in 1973). BTW, note no "O" here: where possible he actually gives the number of machine operations, including the constant factor. TAOCP is very much a "nothing up my sleeve" book, where everything is analyzed down to the constants (where possible) and machine code given.

He starts with a very concrete problem where what's being sorted are numbers that each fit in a machine word:

> “Memory locations R+1, R+2, R+3, R+4, and R+5 contain five numbers. Write a computer program that rearranges these numbers, if necessary, so that they are in ascending order.”

and he makes it clear that what's being sorted are records that contain keys and satellite information, and he's going to mostly assume the keys are integers that fit in a word, sometimes even part of a word. The mention of sorting strings (can get there via the index) is an exercise on page 178:

> Design an algorithm to sort strings α1, ..., αn on an m-letter alphabet into lexicographic order. The total running time of your algorithm should be O(m+n+N), where N = |α1| + · · · + |αn| is the total length of all the strings.

Note that this running time is better than O(n (N/n) log n) — assuming that the strings are of about equal length N/n, and using a standard sorting algorithm — that I mentioned above. The solution is essentially to construct a trie.

• CLRS starts its sorting section with "A sequence of n numbers" and has:

> A sorting algorithm describes the method by which we determine the sorted order, regardless of whether we are sorting individual numbers or large records containing many bytes of satellite data. Thus, when focusing on the problem of sorting, we typically assume that the input consists only of numbers. Translating an algorithm for sorting numbers into a program for sorting records…

Its index on sorting variable-length items points to p206 (in the 3rd edition) where, similar to TAOCP:

> 8-3 Sorting variable-length items

> a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time.

> b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time.