3 ms·
Yes, since every computer has finite memory. If you bubble sort a list of bytes, say your algorithm runs in 10000+n^2 clock cycles. You have at most an exabyte
by rdlw 4y ago
Yes, since every computer has finite memory.
If you bubble sort a list of bytes, say your algorithm runs in 10000+n^2 clock cycles. You have at most an exabyte of storage, so your code will run in at most 10^37 clock cycles! :p
As storage technology improves, of course the coefficient will increase, but at that point is should be considered a different algorithm. This one has undefined behaviour when you have more than an exabyte of storage.
- PeterisP 4y agoThis article has nothing to do with algorithm complexity and "constant time" big-O complexity class, this is about guarantees of code executing in absolutely constant time (i.e. exactly x clock cycles, not "at most") in an input-independent manner to ensure that execution time does not reveal any information about what the inputs/outputs were. In essence, this is about a programming language that can ensure that execution time always equals the worst case; if there's branching, taking both branches and ignoring one of the results; if there's iteration, doing a constant maximum count of iterations no matter what the input data is, etc.