A road named NoNameUno

So what is so important about MTF ?

Well, this has been used widely in some operating systems related coding, and fairly simple and intuitive way to make a LRU linked list. Idea is to move the accessed node into front. The C code is fairly simple. Create a linked list with keys ( or items), and try to access random node of the list, and as you access ( for whatever reasons other than taking out of the list and delete), move the node up in front. Leaving it as an exercise :).

Before we get into some basic foundations for the analysis, lets discuss bit more about what we are up against. Lets take an offline example, meaning that we have aprioi knowlege of the sequence of operations. Now lets say there is an adversery who always access the last item on the list, but we just don't know. In that case, every time we access the give node by our adversery, we will have to traverse the list. So for list with N nodes, we will have O(N^2) for N operations. And surely, we are not achieving any perf gain! This is the absolute worst case. In worst case analysis, this is the upper bound.

First wave of analyses, that made sense came from the idea of giving a reasonable estimate, that make sense... Now we need to discuss what are they and the underlying ideas behind them, before we get into Online algorithm analysis.

Most of the original analysis were based on - Given N operations, what is the worst case, what is the best case, something along this line. Then came average analysis, which happens to depend on probability. As an example, lets say N is 100. So we can have 100 factorial ( 100!) permutation, and in an uniform distribution, one such sequence of 100 has 1 / 100! probability, which is rare in worst case analysis above. Hence came the making sense out of analysis. So it is clear that for small N, say 10, it is highly likely that an absolute pathetic sequence of operations can happen that makes MTF look bad.

But better approach is to use Amortized analysis, because above analysis may not make much sense either !!!

 So what we know so far is that the worst case analysis is pessimistic, stressing the absolute worst case, and not much practical. And probablistic analysis has to base on some probablity metrics/parameters that is only best assumptions. What else, any analysis is not part of crafting the code from an algorithm, it is an analysis technique that gives estimation of time and / or memory complexity, two important resouces of a computing device!