Doubt in understanding the time complexities of algorithms to recognize regular expressions

Question

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al first edition where I came across the following table.

The authors justify the table as follows:

1. Given a regular expression $r$ and an input string $x$, we now have two methods for determining whether $x$ is in $L(r)$. One approach is to use Thompson's Construction to construct an $NFA$ $N$ from $r$. This construction can be done in $O(|r|)$ time, where $|r|$ is the length of $r$. $N$ has at most twice as many states as $|r|$, and at most two transitions from each state, so a transition table for $N$ can be stored in $O(|r|)$ space. We can then use Algorithm 3.4 to determine whether $N$ accepts $x$ in $O(|r| \times |x|)$ time. Thus, using this approach, we can determine whether $x$ is in $L(r)$ in total time proportional to the length of $r$ times the length of $x$.

2. (a) A second approach is to construct a $DFA$ from the regular expression $r$ by applying Thompson's construction to $r$ and then the subset construction, Algorithm 3.2, to the resulting $NFA$.

   (b) Implementing the transition function with a transition table, we can use Algorithm 3.1 to simulate the $DFA$ on input x in time proportional to the length of $x$, independent of the number of states in the $DFA$.

---

Dependencies:

Algorithm 3.4

Algorithm 3.2

Algorithm 3.1

---

Doubt: The point where I am having the doubt is that why are the authors only considering the time complexity of just the algorithm 3.1 and not the time of rest of the work done in the $2(a)$ and $2(b)$. Since the worse case space complexity of the DFA is exponential won't creation of the same involve exponential time as well?

Answer 1

The authors are describing the time complexity to determine whether the input string $x$ is in $L(r)$ in the table and not including construction time, that is they list the per-string cost of using the DFA or NFA, and not the one-time construction cost to build it. In many cases the construction will be done once, and used to recognize strings many times, so it may be worthwhile to sacrifice some time upfront to gain more efficient string recognition afterwards.

You are right to consider the construction cost though. If the automaton will be constructed and used only once, or a small number of times, then the savings in string recognition efficiency may not justify the higher construction time costs.