InforLorV4, Main, Exploration, bibRecordById, Pascal:97-0236853

The average-case complexity of determining the majority

Identifieur interne : 00BD17 ( Main/Exploration ); précédent : 00BD16; suivant : 00BD18

The average-case complexity of determining the majority

Auteurs : L. Alonso [France] ; E. M. Reingold [États-Unis] ; R. Schott [France]

Source :

SIAM journal on computing [ 0097-5397 ] ; 1997.

RBID : Pascal:97-0236853

Descripteurs français

Pascal (Inist)
- Complexité calcul, Analyse algorithme, Arbre décision, Borne inférieure.

English descriptors

KwdEn :
- Algorithm analysis, Computational complexity, Decision tree, Lower bound.

Abstract

Given a set of n elements each of which is either red or blue, it is known that in the worst case n - v(n) pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where v(n) is the number of 1-bits in the binary representation of n. We prove that 2n/3 - √8n/9π + O(logn) such comparisons are necessary and sufficient in the average case.

Affiliations:

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000C70
to stream PascalFrancis, to step Curation: 000C09
to stream PascalFrancis, to step Checkpoint: 000C04
to stream Main, to step Merge: 00C501
to stream Main, to step Curation: 00BD17

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">The average-case complexity of determining the majority</title>
<author><name sortKey="Alonso, L" sort="Alonso, L" uniqKey="Alonso L" first="L." last="Alonso">L. Alonso</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>CRIN, INRIA-Lorraine, Université de Nancy I</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>ENS, 45 Rue d'Ulm</s1>
<s2>75005 Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Reingold, E M" sort="Reingold, E M" uniqKey="Reingold E" first="E. M." last="Reingold">E. M. Reingold</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue</s1>
<s2>Urbana, IL 61801</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>Urbana, IL 61801</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>CRIN, INRIA-Lorraine, Université de Nancy I</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">97-0236853</idno>
<date when="1997">1997</date>
<idno type="stanalyst">PASCAL 97-0236853 INIST</idno>
<idno type="RBID">Pascal:97-0236853</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000C70</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000C09</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000C04</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000C04</idno>
<idno type="wicri:doubleKey">0097-5397:1997:Alonso L:the:average:case</idno>
<idno type="wicri:Area/Main/Merge">00C501</idno>
<idno type="wicri:Area/Main/Curation">00BD17</idno>
<idno type="wicri:Area/Main/Exploration">00BD17</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">The average-case complexity of determining the majority</title>
<author><name sortKey="Alonso, L" sort="Alonso, L" uniqKey="Alonso L" first="L." last="Alonso">L. Alonso</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>CRIN, INRIA-Lorraine, Université de Nancy I</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>ENS, 45 Rue d'Ulm</s1>
<s2>75005 Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Reingold, E M" sort="Reingold, E M" uniqKey="Reingold E" first="E. M." last="Reingold">E. M. Reingold</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue</s1>
<s2>Urbana, IL 61801</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>Urbana, IL 61801</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>CRIN, INRIA-Lorraine, Université de Nancy I</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">SIAM journal on computing</title>
<title level="j" type="abbreviated">SIAM j. comput.</title>
<idno type="ISSN">0097-5397</idno>
<imprint><date when="1997">1997</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">SIAM journal on computing</title>
<title level="j" type="abbreviated">SIAM j. comput.</title>
<idno type="ISSN">0097-5397</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm analysis</term>
<term>Computational complexity</term>
<term>Decision tree</term>
<term>Lower bound</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Complexité calcul</term>
<term>Analyse algorithme</term>
<term>Arbre décision</term>
<term>Borne inférieure</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Given a set of n elements each of which is either red or blue, it is known that in the worst case n - v(n) pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where v(n) is the number of 1-bits in the binary representation of n. We prove that 2n/3 - √8n/9π + O(logn) such comparisons are necessary and sufficient in the average case.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Île-de-France</li>
</region>
<settlement><li>Paris</li>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Alonso, L" sort="Alonso, L" uniqKey="Alonso L" first="L." last="Alonso">L. Alonso</name>
</region>
<name sortKey="Alonso, L" sort="Alonso, L" uniqKey="Alonso L" first="L." last="Alonso">L. Alonso</name>
<name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name>
</country>
<country name="États-Unis"><noRegion><name sortKey="Reingold, E M" sort="Reingold, E M" uniqKey="Reingold E" first="E. M." last="Reingold">E. M. Reingold</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00BD17 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00BD17 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:97-0236853
   |texte=   The average-case complexity of determining the majority
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

The average-case complexity of determining the majority

The average-case complexity of determining the majority

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri