Depends on what you mean by that. You can convert every NFA into a DFA. That's a NP complete (IIRC), but running the DFA is O(n). Running the NFA without converting it is also NP complete. One isn't better than the other, but the costs vary for different expressions and usages.

No, because you can compute the optimal automaton (as in least number of states) that recognizes the same language: https://en.wikipedia.org/wiki/DFA_minimization

The blow up is exponential for carefully crafted academical regular expressions.

im practice is a good idea to build a DFA from your regex, up front (re2) or lazily (ripgrep)