What is the time complexity of Zlib's deflate algorithm?
I understand that in Python this algorithm is made available via the zlib.compress function.
Presumably the corresponding decompression algorithm has the same or better complexity.
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(n) for both compression and decompression. The time scales linearly with the size of the input.
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 n, as opposed to the n. Yes, decompression is usually faster than compression, because that constant is smaller. Not because the time complexity is different, because it isn't.
Time complexity of zlib's deflate algorithm