3 ms·
Please mind that the report was written in 1954. The real complexity of programming and computing in general was not fully understood at that time. (I'm confide
by lifthrasiir 15y ago
Please mind that the report was written in 1954. The real complexity of programming and computing in general was not fully understood at that time. (I'm confident that we still do not understand it in its entirety, however.)
- Edootjuh 15y agoWhat do you mean by that, exactly? Just out of curiosity.
- praptak 15y agoMany results about unfeasibility of computer-based solutions to some problems were not known. For example the first important results about NP-hardness come from the seventies. I believe it wasn't even clear that the big O complexity is important in assessing how effective an algorithm is. This is pretty much obvious to us now (sometimes too obvious - there are some edge cases when the constant factor wins over the asymptotic complexity).
- scott_s 15y agoI agree with everything you said, except the parenthetical. I have difficulty considering matrix multiplication an "edge case," and I think that it's more common than you imply for us to choose algorithms with a higher asymptotic bound because of constant factors and architectural effects (mostly caching).
- praptak 15y agoOk, agreed about matrix multiplication and probably a few other problems, disagreeing about cache. You cannot really say that cache-aware algorithms have higher asymptotic bound. Some of them might happen to have below-optimal asymptotic bound in a cache-unaware memory model, which sort of misses the point of the algorithms being aware of cache.
- scott_s 15y agoYou cannot really say that cache-aware algorithms have higher asymptotic bound. Don't worry, I'm not. I'm saying that sometimes, naive algorithms have better cache behavior than more complicated algorithms with lower asymptotic bounds.
- michaelochurch 15y agoNot grandparent post. I think that one of the differences is that, in 1954, computer programs were single entities written by one person or by a team working closely together. So the "between two pieces of working code" bugs-- which tend to be the nastiest kind in modern development-- weren't really seen yet. Million-line codebases weren't even on the table as a reasonable concept, and the idea of a program depending on 120 other libraries or frameworks was unimaginable.
- scott_s 15y agoI agree with everything above, but I would like to sum it up in my own words: we (as a species) were so new at writing software, that we had no idea of its inherent complexities. Programming was an after-thought for those that designed the first computers.
- Zaak 15y agoAs soon as we started programming, we found to our surprise that it wasn't as easy to get programs right as we had thought. Debugging had to be discovered. I can remember the exact instant when I realized that a large part of my life from then on was going to be spent in finding mistakes in my own programs. — Maurice Wilkes