Time complexity of the decompression algorithm

As previously mentioned, the decompression algorithm is linear with respect to the size of the input. DECOMPRESS requires the helper function DECODE. Let's look at DECODE first.

DECODE has six loop constructs: the while loop on line 4, the while loop on line 13, the for loop on line 21, the for loop on line 24, the while loop on line 29, and the while loop on line 34. All six of these loop constructs do a constant amount of work. Therefore, the function DECODE itself does a constant amount of work. Let's now examine DECOMPRESS.

In DECOMPRESS, the for loop on line 1, and the while loop on line 5, both do a linear amount of work, or $O(n)$ work. The while loop on line 7 does a constant amount of work. DECOMPRESS calls DECODE on line 6, but remember DECODE itself does a constant amount of work. Therefore, DECOMPRESS is linear or does a linear amount of work to decompress input data. If $n$ is the linear size of the input, DECOMPRESS requires time on the order of $O(n)$ to decompress input data.

Figure 6 plots the time it takes to generate random data, and then decompress it. The open circles in the plot represent real data to which the plotted line was fit. If the x-axis or the size of the input is $n$, and if the y-axis or time measured in seconds is $t$, then the equation of the line fitted to the real data is approximately:

$$t = 0.0000006301167n + 0.01284272$$

In other words, in the generation and decompression of random data, the decompression algorithm has overhead of approximately 0.01284272 seconds, and it takes approximately 0.0000006301167 seconds to decompress each byte in the random data.

Figure 6: Size of input vs. Time (Random Data)

Hosted by www.Geocities.ws