The problem is when combining the complement of an expression with another expression (such as when constructing an alternation of the two), because then the complement expression has to be constructed for one of the two, and that can grow double-exponentially in length: https://en.wikipedia.org/wiki/Regular_expression#Expressive_...
