3 ms·
If you wrote a correct binary search algorithm and you observed that, under one language implementation, the time complexity scaled linearly with the size of th
by drdexebtjl 2mo ago
If you wrote a correct binary search algorithm and you observed that, under one language implementation, the time complexity scaled linearly with the size of the input instead of logarithmically, you would think the semantics of the program were changed.
If you used an in-place sort algorithm and observed memory requirements that scale super-linearly with the size of the input, you would think the semantics of the program were changed.
In languages with such tail call guarantees, tail recursion _is_ a loop. It semantically encodes constant space complexity.
- layer8 2mo agoProgramming language semantics as in https://en.wikipedia.org/wiki/Semantics_(programming_languages) https://en.wikipedia.org/wiki/Semantics_(programming_languag... is usually decoupled from space complexity. An interpreter or emulator is considered to preserve language semantics even if it changes time or space complexity.
- drdexebtjl 2mo agoWe're talking about the same thing. I disagree. Such interpreter or emulator would preserve _some_ language semantics, but not all.
- layer8 2mo agoI’m talking about how a programming language specification specifies the semantics of the programming language. It usually does not specify the time and space complexity of its basic operations, be it function calls or arithmetic operators. For example, multiplication could be implemented as O(n) repeated addition instead of in constant time. That would probably be a bad implementation (even on CPUs that only support addition), but it wouldn’t violate the semantics of the programming language.