This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: Opinion of SUSE security about O(n^2) worst case in POWER string ops?
- From: Joseph Myers <joseph at codesourcery dot com>
- To: Rich Felker <dalias at libc dot org>
- Cc: Segher Boessenkool <segher at kernel dot crashing dot org>, Carlos O'Donell <carlos at redhat dot com>, Andreas Schwab <schwab at suse dot de>, Mel Gorman <mgorman at suse dot de>, GNU C Library <libc-alpha at sourceware dot org>
- Date: Fri, 24 Jul 2015 21:34:26 +0000
- Subject: Re: Opinion of SUSE security about O(n^2) worst case in POWER string ops?
- Authentication-results: sourceware.org; auth=none
- References: <55B14DE5 dot 2000209 at redhat dot com> <alpine dot DEB dot 2 dot 10 dot 1507241502560 dot 5465 at digraph dot polyomino dot org dot uk> <20150724165218 dot GA32019 at gate dot crashing dot org> <20150724175557 dot GC16376 at brightrain dot aerifal dot cx>
On Fri, 24 Jul 2015, Rich Felker wrote:
> On Fri, Jul 24, 2015 at 11:52:18AM -0500, Segher Boessenkool wrote:
> > On Fri, Jul 24, 2015 at 03:04:20PM +0000, Joseph Myers wrote:
> > > Note that it is not clear if we do have O(n^2) worst case, or O(2048n) =
> > > O(n). The claim of O(n^2) if m <= 2048 in
> > > <https://sourceware.org/ml/libc-alpha/2015-07/msg00752.html> seems rather
> > > odd to me.
> >
> > I have looked at the code and I don't see it either, it is just O(mn).
>
> O(n^2) was just sloppy language for "quadratic", whereas the real
> quadratic-time for naive strstr algorithms is O(mn). It's still
> quadratic, but in 2 variables rather than one.
And if it's only O(mn) for bounded m, that's linear and not a problem
(although preferably the threshold should be determined based on
benchmarking).
--
Joseph S. Myers
joseph@codesourcery.com