Show simple item record

dc.contributor.authorHirschberg, D.S.
dc.creatorHirschberg, D.S.
dc.date.accessioned 2007-10-31T00:47:05Z
dc.date.available 2007-10-31T00:47:05Z
dc.date.issued 1978-06-20
dc.date.submitted 2003-10-23
dc.identifier.urihttps://hdl.handle.net/1911/19956
dc.description Tech Report
dc.description.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.
dc.language.iso eng
dc.subjectsearching
vector
lower bounds
complexity
dc.title On the Complexity of Vector Searching
dc.type Report
dc.citation.bibtexName techreport
dc.citation.journalTitle Rice University ECE Technical Report
dc.date.modified 2003-10-23
dc.subject.keywordsearching
vector
lower bounds
complexity
dc.citation.issueNumber 7807
dc.type.dcmi Text
dc.type.dcmi Text
dc.identifier.citation D. Hirschberg, "On the Complexity of Vector Searching," Rice University ECE Technical Report, no. 7807, 1978.


Files in this item

Thumbnail

This item appears in the following Collection(s)

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

Show simple item record