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.