fnmatch has exponential running time

[James Youngman]

On 3/22/07, Bruno Haible <bruno@clisp.org> wrote:
> fnmatch() has a worst-case complexity O(m*n) where m is the size of the
> pattern and n is the size of the sample string. Unfortunately glibc has
> chosen an implementation with exponential running time.

Yes.  Oddly, per some testng I did about a year ago, "find -regex" is
much faster than "find -name".  The former uses the Gnulib regex
support and the latter uses fnmatch().

James.