Probabilistic Searching in Sorted Linked Lists
Janko [2] and Bentley, Stanat, and Steele [1] have described probabilistic procedures for data manipulation in sorted linnked lists. Their procedures are based on an algorithm which performs a Member search operation using 2N^1/2 + O(1) expected steps where N is the number of elements in the list. I...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149057 |
| _version_ | 1811073112228233216 |
|---|---|
| author | Leighton, Frank Thomson Lepley, Margaret |
| author_facet | Leighton, Frank Thomson Lepley, Margaret |
| author_sort | Leighton, Frank Thomson |
| collection | MIT |
| description | Janko [2] and Bentley, Stanat, and Steele [1] have described probabilistic procedures for data manipulation in sorted linnked lists. Their procedures are based on an algorithm which performs a Member search operation using 2N^1/2 + O(1) expected steps where N is the number of elements in the list. In addition, Bentley, Stanat and Steele have shown that every Member search algorithm requires (2N)^1/2 + Ω(!) expected steps. In this paper, we improve the lower bound result in order to prove that the known algorithm for Member search is optimal. |
| first_indexed | 2024-09-23T09:28:40Z |
| id | mit-1721.1/149057 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:28:40Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490572023-03-30T04:11:35Z Probabilistic Searching in Sorted Linked Lists Leighton, Frank Thomson Lepley, Margaret Janko [2] and Bentley, Stanat, and Steele [1] have described probabilistic procedures for data manipulation in sorted linnked lists. Their procedures are based on an algorithm which performs a Member search operation using 2N^1/2 + O(1) expected steps where N is the number of elements in the list. In addition, Bentley, Stanat and Steele have shown that every Member search algorithm requires (2N)^1/2 + Ω(!) expected steps. In this paper, we improve the lower bound result in order to prove that the known algorithm for Member search is optimal. 2023-03-29T14:23:42Z 2023-03-29T14:23:42Z 1983-11 https://hdl.handle.net/1721.1/149057 13384760 MIT-LCS-TM-247 application/pdf |
| spellingShingle | Leighton, Frank Thomson Lepley, Margaret Probabilistic Searching in Sorted Linked Lists |
| title | Probabilistic Searching in Sorted Linked Lists |
| title_full | Probabilistic Searching in Sorted Linked Lists |
| title_fullStr | Probabilistic Searching in Sorted Linked Lists |
| title_full_unstemmed | Probabilistic Searching in Sorted Linked Lists |
| title_short | Probabilistic Searching in Sorted Linked Lists |
| title_sort | probabilistic searching in sorted linked lists |
| url | https://hdl.handle.net/1721.1/149057 |
| work_keys_str_mv | AT leightonfrankthomson probabilisticsearchinginsortedlinkedlists AT lepleymargaret probabilisticsearchinginsortedlinkedlists |