Run length encoding

Question

What is the best we can do with run length encoding.

http://en.wikipedia.org/wiki/Run-length_encoding Page suggests the time complexity is O(m*n) where m is the number of time the number repeats ..

Is the a more efficient algorithm to do RLE ??

Answer 1

I think you maybe mis-understood the runtime. The algorithm on the wikipedia page is O(n) (where n is the length of the input). Notice how the index is the same for both loops, and increasing.