# What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why?

Details:

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)$).

The assumption is: the alphabet size is constant, so you can ignore the $b$ factor in the runtime and output size. The second assumption is: you can represent the output DFA as a graph in memory, in a conventional adjacency list data structure (or whatever). So in particular to be able to store an edge from one state to another, you need memory cells that can store up to $n$ bits of information per cell, and (in the standard RAM model) this also means constant-time bitwise operations on these cells.
The idea is: each nonempty set of states of the NFA (corresponding to a single state of the DFA) can be formed by adding one element to a smaller set. So, to compute the transitions for a state $S$: find an element $s$ and a state $R$ such that $S=R\cup\{s\}$. Then, for each input alphabet symbol, compute the transition from $S$ as the bitwise Boolean or of the transition from $R$ (previously computed in the same construction) and the transition from $s$ (in the input NFA). Doing this takes $O(b)$ bitwise Boolean operations per state for a total time of $O(1)$ per state.
In practice, you'd probably rather use the version of the construction that only constructs reachable states, rather than all sets. But when you do it that way you can't be guaranteed to find an element whose removal leaves another reachable state, so your $n$ extra factor in the runtime presumably still applies to this version.
• I do not understand how in your algorithm, you find for each superstate $S$ another superstate $R$ with $S=R \cup \{s\}$ for some NFA state $s$. – DaveBall aka user750378 Dec 12 '14 at 11:15