Technical answer: traditionally,
egrep used a deterministic finite automaton (DFA) internally while
grep used a non-deterministic finite automaton (NFA). These days, GNU
egrep take a hybrid NFA/DFA approach.
According to Friedl's book Mastering Regular Expressions, to discover if your
egrep (for example) has an NFA engine or if it has a DFA engine try:
echo =XX========================================= | egrep 'X(.+)+X'
Freidl (p.147) says:
If it takes a long time to finish, it's an NFA ... If it finishes quickly, it's either a DFA or an NFA with some advanced optimization. Does it display a warning message
about a stack overow or long match aborted? If so, it's an NFA.
Friedl describes the NFA engine as "regex-directed" and the DFA as "text-directed". The details of the distinction are described from p.153 of his book onwards.
The consequence is that there are some pattern/text combinations that are matched more quickly by a DFA and some that are matched more quickly by an NFA. Also, the way you write a regex for an NFA can have a significant effect on the speed of matching. Often, a DFA will be faster, but DFAs do not support lazy matching, they match differently in some cases, they cannot do look-around expressions or back-references, and they omit some other features compared to NFAs.
According to Freidl, GNU
grep uses a DFA when possible and reverts to an NFA when back-references are used.