compressionlz77

Big O time and space complexity of LZ77


What is the Time and space complexities of the LZ77 compression algorithm? I'm trying to implement the algorithm with the best possible space and time complexity


Solution

  • You didn't say with respect to what variable. If you mean the length of the input data, which we will call n, then the time and space is always O(n). LZ77 is applied to a fixed-size window on the data that slides over it, where that size is independent of n.