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: Segher Boessenkool <segher at kernel dot crashing dot org>
- To: Joseph Myers <joseph at codesourcery dot com>
- Cc: "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 11:52:18 -0500
- 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>
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).
2048 seems a tad high (even though you could call it 256) but that
doesn't make the algorithm quadratic.
Unless I missed some path, it is not the most readable code.
Segher