Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6345
Title: Finding Repeated Elements
Authors: Misra, Jayadev
Gries, David
Keywords: computer science
technical report
Issue Date: Jul-1982
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR82-505
Abstract: Two algorithms are presented for finding the values that occur more than $n \div k$ times in array b[O:n-1]. The second algorithm requires time $O(n \log(k))$ and extra space $O(k)$. We prove that $O(n \log(k))$ is a lower bound on the time required for any algorithm based on comparing array elements, so that the second algorithm is optimal. As special cases, determining whether a value occurs more than $n \div 2$ times requires linear time, but determining whether there are duplicates - the case $k=n$ - requires time $O(n \log(n))$. The algorithms may be interesting from a standpoint of programming methodology; each was developed as an extension of an algorithm for the simple case $k=2$.
URI: http://hdl.handle.net/1813/6345
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
82-505.pdf663.03 kBAdobe PDFView/Open
82-505.ps151.04 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us