Time complexity of derivative-based regex matchers
In Theorem 5.2 of his paper, Brzozowski shows that every regular expression has a finite number of dissimilar derivatives, where two regular expressions $r$ and $r'$ are similar if they are ACU-equivalent at the outermost level. That is, consider the equivalence relation generated by the following equivalences:

$$
\array{
r \vee r &amp; \equiv &amp;  r \\
r \vee r' &amp; \equiv &amp; r' \vee r \\
(r \vee r') \vee r'' &amp; \equiv &amp; r \vee (r' \vee r'') \\
r \vee \bot &amp; \equiv &amp; r \\}
$$

(Notice the absence of congruence rules in this definition -- in particular, $a\cdot(r \vee r') \not\equiv a\cdot(r' \vee r)$.) It turns out there are at most $O(2^{|r|})$ many dissimilar word Brzozowski derivatives. So the worst case of matching with Brzozowski derivatives is the same as any other method. 

A nice proof of this fact takes a detour through Antimirov partial derivatives. The one-character Antimirov derivative function is defined as follows:

$$
\array{
a_c(\bot) &amp; = &amp; \emptyset \\
a_c(r \vee r') &amp; = &amp; a_c(r) \cup a_c(r') \\
a_c(\epsilon) &amp; = &amp; \emptyset \\ 
a_c(c')        &amp; = &amp; \emptyset \\
a_c(c)         &amp; = &amp; \{ \epsilon \}  \\
a_c(r_1 \cdot r_2) &amp; = &amp; \{ r'_1 \cdot r_2 \;|\; r'_1 \in a_c(r_1) \} \\
                   &amp;   &amp; \cup \; (\mbox{if}\;\mbox{nullable}(r_1)\;\mbox{then}\; a_c(r_2) \;\mbox{else}\;\emptyset) \\
a_c(r\ast) &amp; = &amp; \{ r' \cdot r\ast \;|\; r' \in a_c(r) \}
}
$$

Basically, instead of returning a single derivative, the Antimirov derivative returns a set of partial derivatives, whose union adds up to the Brzozowski derivative. Now, we can make the following observations:


Up to similarity, the union of the set of Antimirov partial derivatives of a regular expression and the Brzozowski derivative are one and the same. 
It's also easy to prove that given a regular expression $r$, the number of Antimirov word derivatives is linear in the size of $r$. 
Since a Brzozowski derivative is formed from a union of Antimirov derivatives, there can be at most $O(2^{|r|})$ possible Brzozowski derivatives of a regular expression (up to similarity). 


As defined, the Antimirov derivative doesn't work with intersection.     Pascal Caron, Jean-Marc Champarnaud and Ludovic Mignot had a LATA 2011 paper, Partial Derivatives of an Extended Regular Expression, which extended this approach to cover extended regular expressions. Their idea is to define a new partial derivative operation returning a set of sets of partial derivatives (corresponding to DNF), and they show that this has a worst-case exponential size. Intuitively, this corresponds to the fact that implementing intersection on automata uses a product construction.

Anyway, the takeaway (IMO) should be that derivatives are not alternatives to the standard automata-theoretic constructions, but rather are a conceptual explanation of them.