A Fast Natural Algorithm for Searching

Arulanandham, J.J; Calude, C.S; Dinneen, Michael

dc.contributor.author	Arulanandham, J.J	en
dc.contributor.author	Calude, C.S	en
dc.contributor.author	Dinneen, Michael	en
dc.date.accessioned	2009-04-16T23:09:50Z	en
dc.date.available	2009-04-16T23:09:50Z	en
dc.date.issued	2003-06	en
dc.identifier.citation	CDMTCS Research Reports CDMTCS-220 (2003)	en
dc.identifier.issn	1178-3540	en
dc.identifier.uri	http://hdl.handle.net/2292/3727	en
dc.description.abstract	In this note we present two natural algorithms—one for sorting, and another for searching a sorted list of items. Both algorithms work in O(√N) time, N being the size of the list. A combination of these algorithms can search an unsorted list in O(√N) time, an impossibility for classical algorithms. The same complexity is achieved by Grover’s quantum search algorithm; in contrast to Grover’s algorithm which is probabilistic, our method is guaranteed correct. Two applications will conclude this note.	en
dc.publisher	Department of Computer Science, The University of Auckland, New Zealand	en
dc.relation.ispartofseries	CDMTCS Research Report Series	en
dc.rights.uri	https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm	en
dc.source.uri	http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial	en
dc.title	A Fast Natural Algorithm for Searching	en
dc.type	Technical Report	en
dc.subject.marsden	Fields of Research::280000 Information, Computing and Communication Sciences	en
dc.rights.holder	The author(s)	en
dc.rights.accessrights	http://purl.org/eprint/accessRights/OpenAccess	en