I am writing an essay about the Lemepel Ziv Markov chain Algorithm chain 2 and the burrows wheeler transform, but I cannot find the Big O notations for these algorithms. I looked for pseudo code for both, through source code and yet I still cant find the notation. I can only access the LZMA2 Java code, however it is littered with methods from the program I accessed it by (not the IDE). I cannot find the complete raw algorithms for neither of these two algorithms, is there another way I can determine the notation?
Is there a method just by looking at the way they function as compression algorithms?
Thank you very much! Help would be greatly appreciated!
O(n). These methods all work with some fixed block size, with some corresponding approximately constant time to compress a block. So the total time is simply linear in the input size.