10 ms·
But 100x is just a constant factor. What bearing does it have on the asymptotic complexity of the algorithm? (Or to put it differently: It may very well work in
by svat 8y ago
But 100x is just a constant factor. What bearing does it have on the asymptotic complexity of the algorithm? (Or to put it differently: It may very well work in practice, but how does it work in theory?)
- xiphias2 8y agoIf you want to go even further into the details (caching/RAM/Swap), you really get closer to the fact that the communication density between computations is what really matters, and n steps in the Turing machine runs in n*log(n) time in reality.
- xiphias2 8y agoJust a correction: the Random Access Machine needs n*log(n) time, the Turing machine doesn't, as bandwidth is not a problem for the caching layers for sigle threaded execution, just the random access latency.