3 ms·
While a valid observation, there are other physical limits which affect the analysis. For example, assuming constant density and ever increasing sizes (which it
by dalke 14y ago
While a valid observation, there are other physical limits which affect the analysis. For example, assuming constant density and ever increasing sizes (which it does), at some point the computing machine will turn into a black hole. With DNA storage, the density is about that of water and the maximum storage size will be about 10E8 solar masses or about 6 AU. This is a sphere about 50 light minutes in radius, though of course the gravity well will be seriously distorted by this point and the system will need some added reinforcements to handle the rather immense pressures involved.
Any model which assumes constant density will be subject to the same absolute limit, so Ω notation doesn't apply. There is also an upper limit in information density, due to quantum mechanics.
Two other factors apply. Landauer's principle places a lower theoretical limit of energy consumption of a computation. The digital logic to look up something of index N requires at least log2(N) bits of logic for the addressing. You have to cool this off somehow, and the Stefan-Boltzmann law places a limit on how much you can cool in a vacuum. The only resolution is to slow down the system. That might place a higher constraint on the time analysis.
EDIT: Oops! Quite the other way around. The energy needed to keep the entire system warm, despite S-B cooling, will be a limiting factor. Someone else will need to do the full analysis.
And secondly, this assumes there's no need for error handling. As the address size increases, the error rate per address increases exponentially. This requires more space and more heat in order to bring the error rate down to an acceptable threshold. I don't know how to factor that in.
Therefore, instead of worrying about complex physical constraints which are not relevant to just about any computing issue, algorithms analysis uses a specific RAM model, like the trans-dichotomous model.