What's the time / space complexity of pattern matching?

For example, in ReplaceAll[expression, pattern], what are the main algorithms used internally? How does the asymptotic time / space complexity scale with the length / complexity of expression and pattern used above?

• It really depends on the type of pattern. Patterns that require lots of backtracking (e.g., non-trivial combinations of Longest, Shortest, Repeated and/or OrderlessPatternSequence) will be much more expensive than simple ones that just check a head (e.g., _Integer). May 24 at 11:28
• Related Q/A May 24 at 11:39