Content deleted Content added
→History is weird: new section |
|||
Line 138:
I'm not clear on the history, or else I would edit this myself...!
:The brute force algorithm tries <math>O(n^2)</math> different subarrays and takes time <math>O(n)</math> to compute the sum for each of them, giving <math>O(n^3)</math> total. Maybe you are already thinking of optimizing it to be faster? But then it's not the most obvious and basic version of the algorithm any more. And optimizing a bad algorithm is wasted effort. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 04:06, 7 August 2019 (UTC)
== History is weird ==
<blockquote>
Soon after, Shamos described the one-dimensional problem and its history at a Carnegie Mellon University seminar attended by Jay Kadane, who designed within a minute an O(n)-time algorithm, which is clearly as fast as possible.
</blockquote>
The previous comment wonders out loud about the history section, and I have to wonder, too.
<blockquote>
Knuth began the project, originally conceived as a single book with twelve chapters, in 1962.
:
The first three volumes of what was then expected to be a seven-volume set were published in '''1968''', '''1969''', and '''1973'''.
:
Work began in earnest on Volume 4 in 1973, but was suspended in 1977 for work on typesetting.
</blockquote>
Supposedly, this anecdote takes place in 1977. By 1977, if you couldn't derive the O(1) algorithm for the one-dimensional case within 30 minutes, you were seriously in the wrong professional already. The only viable excuse would be a three martini lunch.
What ''really'' was going on here? Because I doubt any of these men were quite that dense upstairs.
For example, I suspect the guy agonizing over the divide and conquer thought he was solving a somewhat generalized version of the problem statement here, for which some of that heavy machinery would have actually been appropriate.
As written, this does not pass my historical smell test. — [[user:MaxEnt|MaxEnt]] 02:09, 12 May 2020 (UTC)
| |||