Computer Science – Data Structures and Algorithms
Scientific paper
2008-05-17
Computer Science
Data Structures and Algorithms
13 pages, 1 figure, Submitted to Journal of Universal Computer Science (J.UCS)
Scientific paper
In the particular case we have insertions/deletions at the tail of a given set S of $n$ one-dimensional elements, we present a simpler and more concrete algorithm than that presented in [Anderson, 2007] achieving the same (but also amortized) upper bound of $O(\sqrt{logd/loglogd})$ for finger searching queries, where $d$ is the number of sorted keys between the finger element and the target element we are looking for. Furthermore, in general case we have insertions/deletions anywhere we present a new randomized algorithm achieving the same expected time bounds. Even the new solutions achieve the optimal bounds in amortized or expected case, the advantage of simplicity is of great importance due to practical merits we gain.
No associations
LandOfFree
Finger Indexed Sets: New Approaches does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Finger Indexed Sets: New Approaches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finger Indexed Sets: New Approaches will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-614516