1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ (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? $\endgroup$ – greybeard Feb 1 at 17:15
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ – Joe1002 Feb 2 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.