News for hackers. Stuff that matters.
Re:FaCT: Constant Time Programming Language by rdlw on Sunday October 23, 2022 @02:52PM (#33309212)
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.

Re:FaCT: Constant Time Programming Language by PeterisP on Sunday October 23, 2022 @04:01PM (#33309782)
This 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.