The construction time for DFA from NFA with $m$ nodes is:

(i) $O(m^2)$
(ii) $O(2^m)$
(iii) $O(m)$
(iv) $O(\log m)$

Question

The construction time for DFA from NFA with $m$ nodes is:

(i) $O(m^2)$  
(ii) $O(2^m)$  
(iii) $O(m)$  
(iv) $O(\log m)$

Accepted Answer

## Answer
**Correct Option: (ii) $O(2^{m})$**

## Explanation
**NFA with $m$ states → DFA via subset construction:**

Number of DFA states $= 2^{m}$ in worst case, and constructing each state requires processing transitions for each symbol ($|\Sigma|$).

Time is proportional to number of subsets times alphabet:

$$T = O(|\Sigma| \cdot 2^{m}) = O(2^{m})$$

(If counting edges, $O(m \cdot 2^{m})$ but dominant exponential.)

Options:
- $O(m^2)$ — polynomial, false for NFA→DFA
- $O(m)$ — linear, false
- $O(\log m)$ — false

### Final Answer
**$O(2^{m})$ → Option (ii)**.

Answer