3 ms·

I don't think it's about that. Technically, everything is finite. But placing limits on the loops and restricting memory allocation bounds the complexity. It pr

by tgv 3y ago

I don't think it's about that. Technically, everything is finite. But placing limits on the loops and restricting memory allocation bounds the complexity. It probably limits everything to P-time.

l33t233372 3y ago
When everything is finite and memory is always limited, what are you meaningfully saying about the possible behaviors of software here?
c_crank 3y ago
Bounding the complexity is desirable for a system that should never fail due to software errors.
adrianN 3y ago
You can easily have bounded loops and superexponential runtime.
- tgv 3y ago
  Without dynamic memory allocation? I think you'd need at least O(n) memory to store enough state to go exponential. But it's some time I did complexity theory; I could be wrong.
  - adrianN 3y ago
    Unless your input is read-only you should always have O(n) memory available.