Some LZ variants such as LZ77 and LZW are O(n), but LZH, for example, is O(n*logn) because of Huffman encoding. I agree that O(n) is not revolutionary, but the simplicity of this algorithm makes it faster to execute.