What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why?
http://en.wikipedia.org/wiki/Powerset_construction states that the worst-case runtime complexity is $\Theta(2^n)$, where $n$ is the number of states of the NFA.
I do not understand how $\Theta(2^n)$ is sufficient: You need up to $2^n$ steps to create the DFA, each creating a new state in the DFA. For each step, you need more time than $\Theta(1)$: you have to consider up to $n$ many states of the NFA (since the DFA-state is a set of up to $n$ states of the NFA) and for each such state up to $b$ (=maximal branching) many outgoing transitions. Thus I would have thought the worst-case time complexity would be $\Theta(2^n \times n \times b)$.
Is there some optimization possible to get to $\Theta(2^n)$? (Above, I have already used the optimization to look in each step at every state of the NFA at most once, instead of iterating through the set of NFA states and for each one doing an epsilon closure with worst case runtime complexity $O(n)$).