| ▲ | ComplexSystems an hour ago | |
This is a very loaded blog post. A unit-cost RAM is a fairly standard model of computation when working with algorithms. When we say that comparison sorting of strings takes O(n log n) time, for instance, we are also implicitly assuming a unit cost for comparing two strings. In real life, comparing two strings scales linearly with string length. Maybe that's silly, but it's par for the course. The original FFT is also assuming unit cost multiplication when we say it is O(n log n) time - we mean O(n log n) multiplies. Similarly, yes, it's a galactic algorithm, but these things are still viewed as meaningful. The fact that it is even possible at all with a unit cost RAM asymptotically is an incredible result that nobody expected. | ||
| ▲ | ttoinou 25 minutes ago | parent [-] | |
Have we settled on a really good universal approximation model of memory+computation or is this a hard topic to solve in itself ? | ||