3 ms·
Note that is is polynomial with respect to the size of the output. That is to say, pathological expressions don't stay small but induce horrendous searching, b
by Ericson2314 5y ago
Note that is is polynomial with respect to the size of the output.
That is to say, pathological expressions don't stay small but induce horrendous searching, but rather merely get a log bigger (and that can cause more trouble for the rest of the program).
That means a heuristic to bail out when something grows a lot probably not violate the users intent and get it back into polynomial time.
- chalst 5y agoNo, this is the time complexity of type checking before any computation on the terms is performed.
- Ericson2314 5y agoYes I am saying that while it is exponential with respect to the input, and it is polynomial with respect to the output.