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?

  • 4
    $\begingroup$ 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). $\endgroup$ May 24, 2021 at 11:28
  • 4
    $\begingroup$ Related Q/A $\endgroup$ May 24, 2021 at 11:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.