4 ms·
> What makes his idea different from everyone else's Depth and coverage. Case in point: Knuth's coverage of Quicksort doesn't calculate the Big-O. It calculat
by dragontamer 8y ago
> What makes his idea different from everyone else's
Depth and coverage.
Case in point: Knuth's coverage of Quicksort doesn't calculate the Big-O. It calculates the precise average running time. He literally counts the assembly-language statements. You might say "But arrays might be randomly sorted", and yeah, Knuth averages the runtime across all possible ways that an array can be sorted. Its a beautiful work of math.
There's almost no room for questions once Knuth finishes a subject. Its so exhaustively covered that I can't even imagine questions I have on any subject after he's done writing about it.
The few questions I do have are the "Difficulty 40+" questions that Knuth puts at the end of each section, which would serve as excellent questions for Masters Thesis or a PH.D Thesis. IE: There's no answer to those questions yet.
Anyway, while most textbooks hand-wave the idea of "Quicksort is faster than Mergesort, even both are O(n*log(n))". Knuth is pretty simple, he says: Look at these two precise numbers I've calculated (and proved). Quicksort is faster (or at least, the Assembly-language version of Quicksort he wrote on his imaginary computer is faster)
Basically, Knuth got "to the bottom of it", there's no hand-waving involved in the explanation. He just tackles the hard questions head on and solves it more precisely than everyone else.
----------
Some of the older chapters are going out of date, which is natural for a work so complete. There is so much material out there that Knuth has to make a decision on whether to revise older stuff (which he does occasionally) or to write about subjects which don't have a major unifying work yet (ie: Constraint Programming has some textbooks here and there, but most of its ideas are only in academic journals, and haven't really been unified into a singular work yet IMO. Even the textbooks on the subjects are mostly introductions + references to papers)
And sometimes, Knuth gets lucky. Knuth's Book3 "Searching and Sorting" includes a HUGE table of sorting methods applied to tape drives.
But today's RAM is now faster sequentially rather than random-access. So Knuth's calculations on Tape-Drive sorts actually applies to modern DDR4 RAM better than any other treatment on the subject. No one else calculated the cost of "internal movements" (aka: cache on modern systems, but it was RAM on older computers) + "external movements" (which was Tape Drives in Knuth TAOCP / Book 3, but is really DDR4 RAM on today's machines).
So yeah, Book 3 is out of date and focuses a huge amount of time on external sorting methods. But... it just so happens that if you know a bit about the sequential nature of modern DDR4 RAM, it is actually super-relevant to today's computers.
- taeric 8y agoThat doesn't sound like it is different, so much as just more complete. His analysis of permutations in order to analyze runtimes is, as you say, truly a wonder. This doesn't feel different from everyone else's idea, though. Unless you just mean in the general complexity analysis, where most of us are basically taught to stop at the highest order terms. It is interesting, because Knuth seems credited with pushing Big-O analysis, but he never stopped at the highest term when analyzing an algorithm. Far as I can tell, he never has. He has done this to compare some algorithms, but even then he has always been empirical for actually comparing things. Treating the Big-O as a hypothesis to test, if anything.