I think the author is trying to capture an idea of “simple”, but has misidentified that as O(n). Any algorithm which operates in a single pass on a stream of data and has a fixed upper memory usage is O(n).
Most other compression implementations also use a hash table, at least on the faster settings. They may switch to something like a hash chain on slower settings, but that doesn't really change asymptotic complexity as it just evaluates more matches.
I don't think any implementation does a straight linear search across the window, as that's just stupidly slow, though maybe a "give me the best compression, I don't care about speed" compressor might.
LZW uses a hash table too (traditionally with a prime based capacity)
I think you oversimplified in the other direction? An algorithm can make 1 pass over data (say it's n bits), then flip through all possible states of those n bits, taking exponential time. Or if you consider that to violate having a "fixed" upper bound (not sure this is meaningful in any useful sense, especially given it would probably need at least log(n) bits to know how far it's read its input), consider that it can even loop infinitely if it wants to.
How do you do that in one pass?
You are right an algorithm doesn't have to be O(n), as it could enter an infinite loop and never finish.
Compare with algorithms that would like to be omniscient but make decisions at every step in order to produce streaming output and/or to forget old state and old inputs, like Viterbi decoding.