Respectively exponential or linear in the input size. The NFA in exchange is exponential in the states (or rather, it's deterministic counterpart is).