Why is regex so slow?

[Johannes Bauer]

On 18.06.2013 22:30, Grant Edwards wrote:

> All the O() tells you is the general shape of the line.

Nitpick: it only gives an *upper bound* for the complexity. Any function
that is within O(n) is also within O(n^2). Usually when people say O()
they actually mean capital Thetha (which is the correct term).

> It's perfectly
> feasible that for the range of values of n that you care about in a
> particular application, there's an O(n^2) algorithm that's way faster
> than another O(log(n)) algorithm.  [Though that becomes a lot less
> likely as n gets large.]

Since O() only gives upper bounds it's also possible for an algorithm
within O(n^2) to always be faster than another algorithm within O(logn).
The O(n^2) algorithm could be Thetha(1).

Regards,
Johannes

-- 
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?
> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
 - Karl Kaos über Rüdiger Thomas in dsa <hidbv3$om2$1 at speranza.aioe.org>