# Running time question

If I have two kinds of LinkedList $$A$$ and $$B$$.

$$A$$ is a move to front one which means:
>>> lst1 = 1, 2, 3, 4, 5, 6, 7, 8, 9
>>> lst1.contain(7)
True
>>> lst1.to_list
7, 1, 2, 3, 4, 5, 6, 8, 9
$$B$$ is a swap list, which means:
>>> lst2 = 1, 2, 3, 4, 5, 6, 7, 8, 9
>>> lst2.contain(7)
True
>>> lst2.to_list
1, 2, 3, 4, 5, 7, 6, 8, 9

I want to find a searching sequence such that the running time of $$B$$ is faster than $$A$$. I mean the Theta of them would be different. The length of lst1 and lst2 are both $$n$$. We search $$m$$ times and can search different elements for different times.

• (3, 1, 2?) Please state in your question: Do you look for one example, for a description of some/all sequences where the sum of the positions of the keys searched is smaller for swap with predecessor, or something else, entirely? Feb 1, 2021 at 17:15

## 2 Answers

The move-to-front heuristic is 4-competitive in the model where swapping adjacent elements costs one unit. This means that if the optimal strategy has cost $$N$$, then move-to-front has cost at most $$4N$$. In particular, if a swap list has cost $$N$$ on some searching sequence, then move-to-front will have cost at most $$4N$$.

See for example MIT OpenCourseWare or Princeton Slides.

The sequence 7, 1 will be ever so slightly faster for $$B$$ than for $$A$$, however, both structures have running time $$O(n)$$ for checking membership and are therefore not particularly suited if this is the main point of the data structure.

The former list is reminiscent of a Least Recently Used (LRU) cache.

• Thank you for your answer. But I need different Big Theta (Big O, whatever). So we cannot use the sequence you raised. But thanks all the same Feb 2, 2021 at 20:43