A Lower Worst-Case Complexity for Searching a Dictionary
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.
Citable link to this pagehttps://hdl.handle.net/1911/19955
MetadataShow full item record
- ECE Publications