  The design and analysis of efficient algorithms with the knowledge of current
and past inputs is a non-trivial and challenging research area in computer
science. In many practical applications the future inputs are not available to
the algorithm at any instance of time. So the algorithm has to make decisions
based on a sequence of inputs that are in order and on the fly. Such algorithms
are known as online algorithms. For measuring the performance of online
algorithms, a standard measure, known as competitive analysis, has been
extensively used in the literature. List update problem is a well studied
research problem in the area of online algorithms since last few decades. One
of the widely used deterministic online list update algorithm is the
Move-To-Front (MTF) algorithm, which has been shown to be 2-competitive with
best performance in practical real life inputs. In this paper we analyse the
Move-to-Front-or-Middle (MFM) algorithm using competitive analysis by
addressing one of an open question raised by Albers that whether dynamic
offline algorithm can be used in finding the competitiveness of an online
algorithm? Move-To-Front-or-Middle (MFM) was experimentally studied and
observed to be performing better than MTF algorithm by using the Calgary Corpus
and Canterbury Corpus data set. However, it is interesting and challenging to
find the lower bound and upper bound on the competitive ratio of MFM algorithm.
We make a first attempt to find the competitiveness of MFM algorithm. Our new
results show that MFM is not 2-competitive with respect to static optimum
offline algorithm, whereas it is 2-competitive with respect to dynamic optimum
offline algorithm. Our new theoretical results may open up a new direction of
research in the online list update problem by characterising the structure of
competitive and non competitive deterministic online algorithms.
