> It's a bit like saying finding the maximum integer in a sorted list is actually order NN because... what if the N ints are all BIGNUMS WITH N bits, huh? I'm

> It's a bit like saying finding the maximum integer in a sorted list is actually order NN because... what if the N ints are all BIGNUMS WITH N bits, huh? I'm not sure I follow. Why would finding the max integer in a sorted list be anything other than the time to copy the last (or first, depending on sort order) element of the list? Certainly a valid point, though, that this isn't a common use case, so that's just not how experts in this field think about this problem. > there are only O(N^(2M)) possible final places where those back-references could match for a single match... huge but if M fixed, not polynomial). Sure, that buys you a pseudo-polynomial algorithm. I just don't like the idea of calling something like that polynomial -- if we did that across the board, then we'd have a poly solution for knapsack (and consequently demonstrate P = NP).