|
Title:
|
A Lower Worst-Case Complexity for Searching a Dictionary |
|
Author:
|
Hirschberg, D.S.
|
|
Type:
|
Tech Report |
|
Keywords:
|
searching |
|
Citation:
|
D. Hirschberg, "A Lower Worst-Case Complexity for Searching a Dictionary," Rice University ECE Technical Report, no. 7808, 1978. |
|
Abstract:
|
It is shown that k(p+3)/2 + p-2 letter comparisons suffice to determine whether a word is a member of a lexicographically ordered dictionary containing 2<sup>p</sup>-1 words of length k. This offers a potential savings (compared to worst case complexity of binary search) that asymptotically approaches 50 percent. |
|
Date Published:
|
1978-07-20 |
