deposit_your_work

A Lower Worst-Case Complexity for Searching a Dictionary

Files in this item

Files Size Format View
Hir1978Jul9ALowerWor.PDF 183.4Kb application/pdf Thumbnail

Show full item record

Item Metadata

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

This item appears in the following Collection(s)

  • ECE Publications [1030 items]
    Publications by Rice University Electrical and Computer Engineering faculty and graduate students