Question

The computation of e-closure of n-states takes ______ time.

(a) O(n^2)

(b) O(n^3)

(c) O(2^n)

(d) None of the mentioned

This question was posed to me in an interview.

My question comes from Conversions among Representations topic in chapter Properties of Regular Languages of Automata Theory

Answer 1

Right answer is (b) O(n^3)

Best explanation: We must search from each of the n states along all arcs labelled e. If there are n states, there can be no more than n^2 states.