Opinion of SUSE security about O(n^2) worst case in POWER string ops?

[Joseph Myers]

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