From mboxrd@z Thu Jan  1 00:00:00 1970
From: Jim Blandy <jimb@zwingli.cygnus.com>
To: Jim Blandy <jimb@cygnus.com>
Cc: Eli Zaretskii <eliz@is.elta.co.il>, dj@redhat.com, gcc@gcc.gnu.org, gdb@sources.redhat.com, binutils@sources.redhat.com, cygwin@sources.redhat.com
Subject: Re: Another RFC: regex in libiberty
Date: Tue, 12 Jun 2001 06:48:00 -0000
Message-id: <np3d95zu49.fsf@zwingli.cygnus.com>
References: <200106080127.VAA01308@greed.delorie.com> <9003-Fri08Jun2001100651+0300-eliz@is.elta.co.il> <nplmmyz1qv.fsf@zwingli.cygnus.com>
X-SW-Source: 2001-06/msg00666.html

Jim Blandy <jimb@cygnus.com> writes:
> To generate every possible match, you have to choose every possible
> way to divide up those twenty a's amongst six .* patterns.  I think
> this is 20 choose 5, or 1.9 million, matches you have to try.  In
> general, I think the time to match POSIXly can increase exponentially
> in the length of your regexp, given a long enough data string.

20 choose 5 is, of course, only 15504, not 1.9 million.  Oops.