Assertion: algorithm | /r/CapableOf | take superpolynomial time
Facets:
value: on a small number of inputs
type: OTHER
Source sentences:
text: An algorithm is said to take superpolynomial time if T(n) is not bounded above by any polynomial.
text: Without the domination condition, this may not be possible since the algorithm which solves L in polynomial time on average may take super-polynomial time on a small number of inputs but f may map these inputs into a much larger set of D' so that algorithm A' no longer runs in polynomial time on average.