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:
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$.
(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$.
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?