Following this transform, files tend to have large regions with locally high frequencies, and compression efficiency is greatly improved by techniques that tend to move frequently-occurring characters toward zero, or the front of the "list".
Due to this, methods and variants of Move-to-Front and frequency counts often follow the BWT algorithm to improve compressibility.
An oblivious adversary has to construct the entire request sequence
before running ALG, and pays the optimal offline price,
Competitive analysis for many list update problems were carried out without any specific knowledge of the exact nature of the optimum offline algorithm (OPT).
[1] The best known optimal offline algorithm dependent on request sequence length runs in O(l^2(l−1)!n) time published by Dr Srikrishnan Divakaran in 2014.
The optimum list update problem was proven to be NP-hard by (Ambühl 2000).
An online algorithm ALG has a competitive ratio c if for any input it performs at least as good as c times worse than OPT.
In a classic result using Potential method analysis (Sleator & Tarjan 1985) proved that MTF is 2-competitive.
The proof does not require the explicit knowledge of OPT but instead counts the number of inversions i.e. elements occurring in opposite order in the lists of MTF and OPT.
The type of adversary doesn't matter in the case of deterministic algorithms, because the adversary can run a copy of the deterministic algorithm on their own to precompute the most disastrous sequence.
It turns out that BIT breaks the deterministic bound - it is better than MTF against oblivious adversaries.
Boris Teia proved a lower bound of 1.5 for any randomized list update algorithm.
In the usual full cost model, an access to an element located at a position i costs i, but the last comparison is inevitable for any algorithm, i.e. there are i-1 elements standing in the way of i.
For the costs of paid transpositions other than unity, Pd models are used.