Regex to NFA to complement So I've found out that a regular expression $n$ symbols long converts to an NFA with $O(n)$ states, it is linear.

Now to go from that NFA to the complement of the NFA, since I can't just flip accept and reject states, this means turning the NFA into a DFA.

If $n$ is the number of states in the NFA, the DFA simulating the NFA can have $2^n$ states.

So would the process of regex to NFA to complement of the NFA be $O(2^n)$?

Trying to figure out what big-O notation it would be.
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$.