Time complexity of the compression algorithm

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

ENCODE has two loop structures: the while loop at line 7, and the while loop at line 21. There are no other loop constructs in ENCODE. Both while loops do a constant amount of work, so the function ENCODE itself does a constant amount of work. Let's now examine COMPRESS.

In COMPRESS, the for loops at lines 2 and 4 do a linear amount of work, or $O(n)$ work. The while loop at line 14, the for loop at line 27, and the while loop at line 32, all do a constant amount of work. COMPRESS calls ENCODE on line 21, but remember ENCODE itself does a constant amount of work. Therefore, COMPRESS is linear or does a linear amount of work to compress input data. If $n$ is the linear size of the input, COMPRESS requires time on the order of $O(n)$ to compress input data.

Figure 5 plots the time it takes to generate random data, and then compress 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.000077059n + 0.3867179$$

In other words, in the generation and compression of random data, the compression algorithm has overhead of approximately 0.3867179 seconds, and it takes approximately 0.00007705963 seconds to compress each byte in the random data.

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

Hosted by www.Geocities.ws