CODEWITHSUNDEEP
compressiontime-complexityjpegcpu-usage
zacdawg
zacdawg

Reputation: 35

JPEG-Compression, Time Complexity and Performance

I have a few questions regarding JPEG-compression;

What is the typical time-complexity of a good implementation of a JPEG-compression algorithm? I've tried reading up on the process itself but as it turns out I find it quite hard to pinpoint exactly what processes that needs to be done - I'm still at a pretty basic level in my algorithm-knowledge.. :-)

And I also wonder (I guess this can be derived from the first question) how demanding JPEG-compression is for the CPU compared to different compression algorithms, e.g. .gif - say if I needed to compress 1000 photos for example.

Upvotes: 0

Views: 2778

Answers (1)

Mark Adler
Mark Adler

Reputation: 112349

If you mean as a function of the size of the image, it's linear. The compression and decompression time are O(n), where n is the number of pixels.

JPEG and GIF are two different solutions to two different problems. JPEG is lossy generally for natural, photographic images, whereas GIF is lossless, generally for simple graphic images and icons. You would not use GIF for photographs.

Also GIF is obsolete, having been replaced with PNG, except for simple animated GIFs, of cats mostly. (There are better methods for lossless image compression than what PNG uses, but none seem to have caught on. The compression methods in PNG should be obsolete, but they aren't.)

Upvotes: 0

Related Questions