For the time-bounded classes, we show a weaker result.

Theorem 1.23

Proof

A nondecreasing function f(n) is called superpolynomial if

for all i ≥ 1. For instance, the exponential function 2n is superpolynomial, ...

Get Theory of Computational Complexity, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.