I have this assignment where i need to use an algorithm called jumpset to implement search in a sorted linked list L.
The jumpset algorithm assigns 1 or more "jump" pointers to each object in L.
Initially x.jump is set to x.next for each object x in L
Then a loop is entered which continues so long L.head.jump!=NIL.
For each iteration i of this loop an inner loop is initiated which traverses the objects in L, skipping 2i objects per iteration.
So for example, for a list of length 10 we get
1st iteration:
L[1].jump.= L[3]
L[3].jump=L[5]
L[5].jump=L[7]
L[7].jump=L[9]
L[9].jump=NIL
2nd iteration
L[1].jump=L[5]
L[5].jump=L[9]
3rd iteration
L[1].jump=L[9]
4th iteration
L[1].jump=NIL
I believe i understand how to search for an object x using the pointers generated by the above algorithm. If we store the pointers assigned to x in x.p, you just start with L.head.p and follow its trail of pointers until you reach an object y equal to or larger than x. if x=y you return TRUE, else you repeat the same process L[y].
Eventually, if x is not in L you will reach a NIL object from which there are no pointers and so you return FALSE.
My problem is i cannot figure out the runtime of this method.
Obviously its O(n), but the naive solution for insertion into a linked list has O(n) time too, so it seems reasonable to assume this method would lower the boundary. Why else should we bother with this method?
I hope someone can help me.
if needed here is the original specification of the algorithM for jumpset:
