Many stream-based compressors don't track how far they have read into their input, they just keep reading bytes, and writing out bytes. Things like zlib can be

Many stream-based compressors don't track how far they have read into their input, they just keep reading bytes, and writing out bytes. Things like zlib can be set up with a fixed sized buffer, and don't go allocating extra memory, so they definately can't start using arbitary extra space. You are right an algorithm doesn't have to be O(n), as it could enter an infinite loop and never finish.