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: Rich Felker <dalias at libc dot org>
- To: Segher Boessenkool <segher at kernel dot crashing dot org>
- Cc: Joseph Myers <joseph at codesourcery dot com>, 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 13:55:57 -0400
- 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>
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.
Rich