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." 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!)
Anyway, the point is that it's O(n/m) in the usual case. Which remains technically linear, not sub-linear; but at least it's O(n) with a constant factor smaller than 1.
dataflow|1 year ago
quuxplusone|1 year ago
Anyway, the point is that it's O(n/m) in the usual case. Which remains technically linear, not sub-linear; but at least it's O(n) with a constant factor smaller than 1.