&gt; The conversion from DFA to NFA [...]<p>I believe you mean NFA to DFA.<p>&gt; [...] would require O(n^2) in that case<p>I believe you mean O(2^n).
<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Powerset_construction#Complexity" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Powerset_construction#Complexi...</a>