On the Complexity of Vector Searching

Files in this item

Files Size Format View
Hir1978Jun9OntheComp.PDF 519.5Kb application/pdf Thumbnail

Show full item record

Item Metadata

Title: On the Complexity of Vector Searching
Author: Hirschberg, D.S.
Type: Report
xmlui.Rice_ECE.Keywords: searching; vector; lower bounds; complexity
Citation: D. Hirschberg, "On the Complexity of Vector Searching," Rice University ECE Technical Report, no. 7807, 1978.
Abstract: The vector searching problem is, given k-vector A (a k-vector) is a vector that has k components, over the integers) and given a set B of n distinct k-vectors, to determine whether or not A is a member of set B. Comparisons between components yielding "greater than-equal-less than" results are permitted. It is shown that if the vectors in B are unordered then nk comparisons are necessary and sufficient. In the case when the vectors in B are ordered, it is shown that [log n] + k comparisons are necessary and, for n≥4k, k[log(n/k)] + 2k-1 comparisons are sufficient.
Date Published: 1978-06-20

This item appears in the following Collection(s)

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