Cost in time of constructing and running an NFA vs DFA for a given regex
Kiliki's answer has some things wrong.

They say:


  The construction time for an NFA should be O(m), where m is the number of nodes (don't quote me on that one, it's more of a semi-logical assumption than anything)


This doesn't even really make sense. If you are constructing a NFA from a regular expression there are no well defined "nodes" to speak of. A sufficient algorithm is the Thompson's construction. 

Amortized time for constructing an NFA from a regular expression

A regular expression is composed literal characters stuck together in various ways


concatenation
alteration and
Kleene star.


Thompson's construction defines rules for making an NFA for literal characters. For the character 'x' where Os are states. 

       x
    O ---&gt; O


There are other rules for concatenation, etc. that join together NFA's like the one above, but the important part is that any operation adds a small finite number of states and transitions (never more than two states or four transitions actually. If you want the details have a look at the super helpful wiki link above). 

The number of literals and operations (concatenation, etc.) is easily determined from the length of the string of the regular expression. The amount of one or the other is different only by a constant factor. Thus we can safely say that constructing an NFA from a regular expression using Thompson's construction is O(n) where n is the length of the string of the regular expression.