2 ms·
The statically determined upper bound can vastly overestimate the actual runtime complexity in common cases, because it generally can’t predict how conditionals
by layer8 2y ago
The statically determined upper bound can vastly overestimate the actual runtime complexity in common cases, because it generally can’t predict how conditionals that lead to early exits in recursions will turn out.
Note: This assumes lazy evaluation, or short-circuiting conditionals, in order for early exits to affect the runtime, but that’s what you’d generally have in a practical language.