7 ms·

I don’t believe space > time is possible on a Turing machine?

• pjscott 2y ago
  You’re right, of course, but there was a minor miscommunication: the exponential space is exponentially proportional to the size of the regular expression, and the linear time is linearly proportional to the length of the string being searched through.
  • dullcrisp 2y ago
    Thanks! Though I imagine in most cases the regular expression itself would be a fixed part of the codebase and not given as input.