> No, it's O(n) worst case. (The Wikipedia sidebar says "O(mn)," but that's apparently for a maimed version of the algorithm without a key part they're calling "the Galil rule.")
It's not "maimed", it's literally the original algorithm. And what the article was specifically analyzing. And exactly what the parent was citing. "No" here makes no sense, unless your goal was just to write "no" to someone on the internet.
> That's a special usage of the phrase "worst case"! In the absolute worst case, your implementation could have a bug and never terminate at all!
Wikipedia is describing that algorithm, not a different broken one. If your code is buggy then you're not implementing that algorithm, you're implementing a different one that happens to be buggy. It's completely absurd to suggest "the absolute worst case" of an algorithm could include that of a different algorithm. Whether the latter is correct or buggy.
> Anyway, the point is that it's O(n/m) in the usual case.
Sure, and the halting problem is O(1) in the best case.
> Which remains technically linear, not sub-linear
So it's neither an example of what the page was talking about (sublinear) nor an answer to my question (interesting sublinear).
> but at least it's O(n) with a constant factor smaller than 1.
If "usually only reads a fraction of the input" was what I was looking for, I would've realized String.indexOf(char) or Array.find(element) is an answer, and not needed to ask a question here.
It's not "maimed", it's literally the original algorithm. And what the article was specifically analyzing. And exactly what the parent was citing. "No" here makes no sense, unless your goal was just to write "no" to someone on the internet.
> That's a special usage of the phrase "worst case"! In the absolute worst case, your implementation could have a bug and never terminate at all!
Wikipedia is describing that algorithm, not a different broken one. If your code is buggy then you're not implementing that algorithm, you're implementing a different one that happens to be buggy. It's completely absurd to suggest "the absolute worst case" of an algorithm could include that of a different algorithm. Whether the latter is correct or buggy.
> Anyway, the point is that it's O(n/m) in the usual case.
Sure, and the halting problem is O(1) in the best case.
> Which remains technically linear, not sub-linear
So it's neither an example of what the page was talking about (sublinear) nor an answer to my question (interesting sublinear).
> but at least it's O(n) with a constant factor smaller than 1.
If "usually only reads a fraction of the input" was what I was looking for, I would've realized String.indexOf(char) or Array.find(element) is an answer, and not needed to ask a question here.