Time complexity of zlib's deflate algorithm
<p>What is the time complexity of Zlib's deflate algorithm?</p>

<p>I understand that in Python this algorithm is made available via the <code>zlib.compress</code> function.</p>

<p>Presumably the corresponding decompression algorithm has the same or better complexity.</p>

<p>Time complexity is how the processing time scales with the size of the input. For zlib, and any other compression scheme I know of, it is O(<em>n</em>) for both compression and decompression. The time scales linearly with the size of the input.</p>

<p>If you are thinking that the time complexity of decompression is less somehow, then perhaps you are thinking about the constant in front of the <em>n</em>, as opposed to the <em>n</em>. Yes, decompression is usually faster than compression, because that constant is smaller. Not because the time complexity is different, because it isn't.</p>

python compression complexity-theory zlib