Regex to NFA to complement
No.  As you said, the NFA can have $m=O(n)$ states, and the DFA can have as many as $2^m$ states, so the DFA can have as many $2^{O(n)}$ states.  Consequently, converting a regexp to a NFA and then complementing the NFA can yield an automaton with $2^{O(n)}$ states.  $2^{O(n)}$ is larger than $O(2^n)$: notice the difference between $2^{cn}$ vs $c \cdot 2^n$.