Gupta; Verdu (Lossy Compression Data Compression)
Jump to navigation
Jump to search
Time Complexity
$O(n^{2} log^{3} n)$
Space Complexity
$O(n)$ bits
(Derived: Considering the codebook to be part of the input, this only requires storing a single codeword in memory, of size $O(n)$, along with some constants)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
2009