File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/0020-0190(94)90052-3
- Scopus: eid_2-s2.0-0028199378
- WOS: WOS:A1994MV42200007
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: A randomized algorithm for finding maximum with O((log n)2) polynomial tests
| Title | A randomized algorithm for finding maximum with O((log n)2) polynomial tests |
|---|---|
| Authors | |
| Keywords | Algorithms Decision Trees Maximum Parity Tests Randomized Algorithms |
| Issue Date | 1994 |
| Publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl |
| Citation | Information Processing Letters, 1994, v. 49 n. 1, p. 39-43 How to Cite? |
| Abstract | A well-known result by Rabin implies that n • 1 polynomial tests are necessary and sufficient in the worst case to find the maximum of n distinct real numbers. In this note we show that, for any fixed constant c> 0, there is a randomized agorithm with error probability O(n-c) for finding the maximum of n distinct real numbers using only O((log n)2) polynomial tests. |
| Persistent Identifier | http://hdl.handle.net/10722/152244 |
| ISSN | 2023 Impact Factor: 0.7 2023 SCImago Journal Rankings: 0.404 |
| ISI Accession Number ID |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Ting, HF | en_US |
| dc.contributor.author | Yao, AC | en_US |
| dc.date.accessioned | 2012-06-26T06:36:43Z | - |
| dc.date.available | 2012-06-26T06:36:43Z | - |
| dc.date.issued | 1994 | en_US |
| dc.identifier.citation | Information Processing Letters, 1994, v. 49 n. 1, p. 39-43 | en_US |
| dc.identifier.issn | 0020-0190 | en_US |
| dc.identifier.uri | http://hdl.handle.net/10722/152244 | - |
| dc.description.abstract | A well-known result by Rabin implies that n • 1 polynomial tests are necessary and sufficient in the worst case to find the maximum of n distinct real numbers. In this note we show that, for any fixed constant c> 0, there is a randomized agorithm with error probability O(n-c) for finding the maximum of n distinct real numbers using only O((log n)2) polynomial tests. | en_US |
| dc.language | eng | en_US |
| dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl | en_US |
| dc.relation.ispartof | Information Processing Letters | en_US |
| dc.subject | Algorithms | en_US |
| dc.subject | Decision Trees | en_US |
| dc.subject | Maximum | en_US |
| dc.subject | Parity Tests | en_US |
| dc.subject | Randomized Algorithms | en_US |
| dc.title | A randomized algorithm for finding maximum with O((log n)2) polynomial tests | en_US |
| dc.type | Article | en_US |
| dc.identifier.email | Ting, HF:hfting@cs.hku.hk | en_US |
| dc.identifier.authority | Ting, HF=rp00177 | en_US |
| dc.description.nature | link_to_subscribed_fulltext | en_US |
| dc.identifier.doi | 10.1016/0020-0190(94)90052-3 | en_US |
| dc.identifier.scopus | eid_2-s2.0-0028199378 | en_US |
| dc.identifier.volume | 49 | en_US |
| dc.identifier.issue | 1 | en_US |
| dc.identifier.spage | 39 | en_US |
| dc.identifier.epage | 43 | en_US |
| dc.identifier.isi | WOS:A1994MV42200007 | - |
| dc.publisher.place | Netherlands | en_US |
| dc.identifier.scopusauthorid | Ting, HF=7005654198 | en_US |
| dc.identifier.scopusauthorid | Yao, AC=7101796460 | en_US |
| dc.identifier.issnl | 0020-0190 | - |