Fragile complexity of adaptive algorithms Article Swipe
Prosenjit Bose
,
Pilar Cano
,
Rolf Fagerberg
,
John Iacono
,
Riko Jacob
,
Stefan Langerman
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.1016/j.tcs.2022.03.034
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.1016/j.tcs.2022.03.034
The fragile complexity of a comparison-based algorithm is $f(n)$ if each input
element participates in $O(f(n))$ comparisons.
In this paper, we explore the fragile complexity of algorithms adaptive to
various restrictions on the input, i.e., algorithms with a fragile complexity
parameterized by a quantity other than the input size~$n$. We show
that searching for the predecessor in a sorted array has fragile complexity
$\Theta(\log k)$, where $k$ is the rank of the query element, both
in a randomized and a deterministic setting. For predecessor
searches, we also show how to optimally reduce the amortized fragile complexity
of the elements in the array. We also prove the following results:
Selecting the $k$th smallest element has expected fragile complexity
$O(\log\log k)$ for the element selected. Deterministically finding
the minimum element has fragile complexity $\Theta(\log(\INV))$ and
$\Theta(\log(\RUNS))$, where $\INV$ is the number of inversions in a
sequence and $\RUNS$ is the number of increasing runs in a sequence.
Deterministically finding the median has fragile complexity
$O(\log(\RUNS) + \log\log n)$ and $\Theta(\log (\INV))$.
Deterministic sorting has fragile complexity $\Theta(\log (\INV))$ but it has
fragile complexity $\Theta(\log n)$ regardless of the number of runs.
Related Topics
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://pure.itu.dk/portal/da/publications/2882662a-bc42-4374-b671-d809ffa2759e
- OA Status
- green
- Cited By
- 1
- References
- 20
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4220841793
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4220841793Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1016/j.tcs.2022.03.034Digital Object Identifier
- Title
-
Fragile complexity of adaptive algorithmsWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-06-05Full publication date if available
- Authors
-
Prosenjit Bose, Pilar Cano, Rolf Fagerberg, John Iacono, Riko Jacob, Stefan LangermanList of authors in order
- Landing page
-
https://pure.itu.dk/portal/da/publications/2882662a-bc42-4374-b671-d809ffa2759ePublisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://pure.itu.dk/portal/da/publications/2882662a-bc42-4374-b671-d809ffa2759eDirect OA link when available
- Concepts
-
Algorithm, Computer science, Mathematics, Theoretical computer scienceTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2021: 1Per-year citation counts (last 5 years)
- References (count)
-
20Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4220841793 |
|---|---|
| doi | https://doi.org/10.1016/j.tcs.2022.03.034 |
| ids.openalex | https://openalex.org/W4220841793 |
| fwci | 0.0 |
| type | article |
| title | Fragile complexity of adaptive algorithms |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11321 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9990000128746033 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1705 |
| topics[0].subfield.display_name | Computer Networks and Communications |
| topics[0].display_name | Error Correcting Code Techniques |
| topics[1].id | https://openalex.org/T11269 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9944999814033508 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Algorithms and Data Compression |
| topics[2].id | https://openalex.org/T10125 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9916999936103821 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2208 |
| topics[2].subfield.display_name | Electrical and Electronic Engineering |
| topics[2].display_name | Advanced Wireless Communication Techniques |
| funders[0].id | https://openalex.org/F4320309617 |
| funders[0].ror | https://ror.org/04rw64z44 |
| funders[0].display_name | National Foundation for Science and Technology Development |
| funders[1].id | https://openalex.org/F4320321390 |
| funders[1].ror | https://ror.org/03q83t159 |
| funders[1].display_name | Fonds De La Recherche Scientifique - FNRS |
| funders[2].id | https://openalex.org/F4320322928 |
| funders[2].ror | https://ror.org/02sptwz63 |
| funders[2].display_name | Danmarks Frie Forskningsfond |
| funders[3].id | https://openalex.org/F4320334593 |
| funders[3].ror | https://ror.org/01h531d29 |
| funders[3].display_name | Natural Sciences and Engineering Research Council of Canada |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C11413529 |
| concepts[0].level | 1 |
| concepts[0].score | 0.5474640727043152 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[0].display_name | Algorithm |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.5006523132324219 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C33923547 |
| concepts[2].level | 0 |
| concepts[2].score | 0.33219361305236816 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[2].display_name | Mathematics |
| concepts[3].id | https://openalex.org/C80444323 |
| concepts[3].level | 1 |
| concepts[3].score | 0.3222368359565735 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[3].display_name | Theoretical computer science |
| keywords[0].id | https://openalex.org/keywords/algorithm |
| keywords[0].score | 0.5474640727043152 |
| keywords[0].display_name | Algorithm |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.5006523132324219 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/mathematics |
| keywords[2].score | 0.33219361305236816 |
| keywords[2].display_name | Mathematics |
| keywords[3].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[3].score | 0.3222368359565735 |
| keywords[3].display_name | Theoretical computer science |
| language | en |
| locations[0].id | pmh:oai:pure.atira.dk:publications/2882662a-bc42-4374-b671-d809ffa2759e |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400216 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Research Portal (King's College London) |
| locations[0].source.host_organization | https://openalex.org/I183935753 |
| locations[0].source.host_organization_name | King's College London |
| locations[0].source.host_organization_lineage | https://openalex.org/I183935753 |
| locations[0].license | cc-by-nc-sa |
| locations[0].pdf_url | |
| locations[0].version | submittedVersion |
| locations[0].raw_type | info:eu-repo/semantics/publishedVersion |
| locations[0].license_id | https://openalex.org/licenses/cc-by-nc-sa |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | Jacob, R, Fagerberg, R, Bose, P, Cano, P, Iacono, J & Langerman, S 2022, 'Fragile complexity of adaptive algorithms', Theoretical Computer Science, vol. 915, pp. 92-102. https://doi.org/10.1016/j.tcs.2022.03.034 |
| locations[0].landing_page_url | https://pure.itu.dk/portal/da/publications/2882662a-bc42-4374-b671-d809ffa2759e |
| authorships[0].author.id | https://openalex.org/A5013674788 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-8906-0573 |
| authorships[0].author.display_name | Prosenjit Bose |
| authorships[0].countries | CA |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I67031392 |
| authorships[0].affiliations[0].raw_affiliation_string | School of Computer Science, Carleton University, Canada |
| authorships[0].institutions[0].id | https://openalex.org/I67031392 |
| authorships[0].institutions[0].ror | https://ror.org/02qtvee93 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I67031392 |
| authorships[0].institutions[0].country_code | CA |
| authorships[0].institutions[0].display_name | Carleton University |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Prosenjit Bose |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | School of Computer Science, Carleton University, Canada |
| authorships[1].author.id | https://openalex.org/A5035971199 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-4318-5282 |
| authorships[1].author.display_name | Pilar Cano |
| authorships[1].countries | BE |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I132053463 |
| authorships[1].affiliations[0].raw_affiliation_string | Université libre de Bruxelles, Belgium |
| authorships[1].institutions[0].id | https://openalex.org/I132053463 |
| authorships[1].institutions[0].ror | https://ror.org/01r9htc13 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I132053463 |
| authorships[1].institutions[0].country_code | BE |
| authorships[1].institutions[0].display_name | Université Libre de Bruxelles |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Pilar Cano |
| authorships[1].is_corresponding | True |
| authorships[1].raw_affiliation_strings | Université libre de Bruxelles, Belgium |
| authorships[2].author.id | https://openalex.org/A5021765002 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-1004-3314 |
| authorships[2].author.display_name | Rolf Fagerberg |
| authorships[2].countries | DK |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I177969490 |
| authorships[2].affiliations[0].raw_affiliation_string | University of Southern Denmark, Denmark |
| authorships[2].institutions[0].id | https://openalex.org/I177969490 |
| authorships[2].institutions[0].ror | https://ror.org/03yrrjy16 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I177969490 |
| authorships[2].institutions[0].country_code | DK |
| authorships[2].institutions[0].display_name | University of Southern Denmark |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Rolf Fagerberg |
| authorships[2].is_corresponding | True |
| authorships[2].raw_affiliation_strings | University of Southern Denmark, Denmark |
| authorships[3].author.id | https://openalex.org/A5088852372 |
| authorships[3].author.orcid | https://orcid.org/0000-0001-8885-8172 |
| authorships[3].author.display_name | John Iacono |
| authorships[3].countries | BE, US |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I57206974 |
| authorships[3].affiliations[0].raw_affiliation_string | New York University, USA |
| authorships[3].affiliations[1].institution_ids | https://openalex.org/I132053463 |
| authorships[3].affiliations[1].raw_affiliation_string | Université libre de Bruxelles, Belgium |
| authorships[3].institutions[0].id | https://openalex.org/I132053463 |
| authorships[3].institutions[0].ror | https://ror.org/01r9htc13 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I132053463 |
| authorships[3].institutions[0].country_code | BE |
| authorships[3].institutions[0].display_name | Université Libre de Bruxelles |
| authorships[3].institutions[1].id | https://openalex.org/I57206974 |
| authorships[3].institutions[1].ror | https://ror.org/0190ak572 |
| authorships[3].institutions[1].type | education |
| authorships[3].institutions[1].lineage | https://openalex.org/I57206974 |
| authorships[3].institutions[1].country_code | US |
| authorships[3].institutions[1].display_name | New York University |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | John Iacono |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | New York University, USA, Université libre de Bruxelles, Belgium |
| authorships[4].author.id | https://openalex.org/A5072095949 |
| authorships[4].author.orcid | https://orcid.org/0000-0001-9470-1809 |
| authorships[4].author.display_name | Riko Jacob |
| authorships[4].countries | DK |
| authorships[4].affiliations[0].institution_ids | https://openalex.org/I83467386 |
| authorships[4].affiliations[0].raw_affiliation_string | IT University of Copenhagen, Denmark |
| authorships[4].institutions[0].id | https://openalex.org/I83467386 |
| authorships[4].institutions[0].ror | https://ror.org/02309jg23 |
| authorships[4].institutions[0].type | education |
| authorships[4].institutions[0].lineage | https://openalex.org/I83467386 |
| authorships[4].institutions[0].country_code | DK |
| authorships[4].institutions[0].display_name | IT University of Copenhagen |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Riko Jacob |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | IT University of Copenhagen, Denmark |
| authorships[5].author.id | https://openalex.org/A5072214666 |
| authorships[5].author.orcid | https://orcid.org/0000-0001-6999-3088 |
| authorships[5].author.display_name | Stefan Langerman |
| authorships[5].countries | BE |
| authorships[5].affiliations[0].institution_ids | https://openalex.org/I132053463 |
| authorships[5].affiliations[0].raw_affiliation_string | Université libre de Bruxelles, Belgium |
| authorships[5].institutions[0].id | https://openalex.org/I132053463 |
| authorships[5].institutions[0].ror | https://ror.org/01r9htc13 |
| authorships[5].institutions[0].type | education |
| authorships[5].institutions[0].lineage | https://openalex.org/I132053463 |
| authorships[5].institutions[0].country_code | BE |
| authorships[5].institutions[0].display_name | Université Libre de Bruxelles |
| authorships[5].author_position | last |
| authorships[5].raw_author_name | Stefan Langerman |
| authorships[5].is_corresponding | False |
| authorships[5].raw_affiliation_strings | Université libre de Bruxelles, Belgium |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://pure.itu.dk/portal/da/publications/2882662a-bc42-4374-b671-d809ffa2759e |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Fragile complexity of adaptive algorithms |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-12-10T02:45:41.426853 |
| primary_topic.id | https://openalex.org/T11321 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9990000128746033 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1705 |
| primary_topic.subfield.display_name | Computer Networks and Communications |
| primary_topic.display_name | Error Correcting Code Techniques |
| related_works | https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2051487156, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2021 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 1 |
| best_oa_location.id | pmh:oai:pure.atira.dk:publications/2882662a-bc42-4374-b671-d809ffa2759e |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400216 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Research Portal (King's College London) |
| best_oa_location.source.host_organization | https://openalex.org/I183935753 |
| best_oa_location.source.host_organization_name | King's College London |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I183935753 |
| best_oa_location.license | cc-by-nc-sa |
| best_oa_location.pdf_url | |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | info:eu-repo/semantics/publishedVersion |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by-nc-sa |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | Jacob, R, Fagerberg, R, Bose, P, Cano, P, Iacono, J & Langerman, S 2022, 'Fragile complexity of adaptive algorithms', Theoretical Computer Science, vol. 915, pp. 92-102. https://doi.org/10.1016/j.tcs.2022.03.034 |
| best_oa_location.landing_page_url | https://pure.itu.dk/portal/da/publications/2882662a-bc42-4374-b671-d809ffa2759e |
| primary_location.id | pmh:oai:pure.atira.dk:publications/2882662a-bc42-4374-b671-d809ffa2759e |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400216 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Research Portal (King's College London) |
| primary_location.source.host_organization | https://openalex.org/I183935753 |
| primary_location.source.host_organization_name | King's College London |
| primary_location.source.host_organization_lineage | https://openalex.org/I183935753 |
| primary_location.license | cc-by-nc-sa |
| primary_location.pdf_url | |
| primary_location.version | submittedVersion |
| primary_location.raw_type | info:eu-repo/semantics/publishedVersion |
| primary_location.license_id | https://openalex.org/licenses/cc-by-nc-sa |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | Jacob, R, Fagerberg, R, Bose, P, Cano, P, Iacono, J & Langerman, S 2022, 'Fragile complexity of adaptive algorithms', Theoretical Computer Science, vol. 915, pp. 92-102. https://doi.org/10.1016/j.tcs.2022.03.034 |
| primary_location.landing_page_url | https://pure.itu.dk/portal/da/publications/2882662a-bc42-4374-b671-d809ffa2759e |
| publication_date | 2022-06-05 |
| publication_year | 2022 |
| referenced_works | https://openalex.org/W2033516840, https://openalex.org/W4411319177, https://openalex.org/W2078284127, https://openalex.org/W1996578733, https://openalex.org/W2018047324, https://openalex.org/W2504812378, https://openalex.org/W1968119892, https://openalex.org/W2185212870, https://openalex.org/W4205550388, https://openalex.org/W2066823629, https://openalex.org/W2034955722, https://openalex.org/W2017461851, https://openalex.org/W2096006817, https://openalex.org/W1587590810, https://openalex.org/W4300354056, https://openalex.org/W1483444214, https://openalex.org/W4206441762, https://openalex.org/W2043266636, https://openalex.org/W1494057369, https://openalex.org/W2914951704 |
| referenced_works_count | 20 |
| abstract_inverted_index.+ | 147 |
| abstract_inverted_index.a | 4, 34, 38, 52, 69, 72, 139 |
| abstract_inverted_index.We | 45, 93 |
| abstract_inverted_index.by | 37 |
| abstract_inverted_index.if | 9 |
| abstract_inverted_index.in | 13, 51, 90, 128, 138 |
| abstract_inverted_index.is | 7, 61, 123, 132 |
| abstract_inverted_index.it | 160 |
| abstract_inverted_index.of | 3, 23, 64, 126, 135, 166, 169 |
| abstract_inverted_index.on | 28 |
| abstract_inverted_index.to | 81 |
| abstract_inverted_index.we | 18, 77 |
| abstract_inverted_index.$k$ | 60 |
| abstract_inverted_index.For | 75 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 71, 130, 150 |
| abstract_inverted_index.but | 159 |
| abstract_inverted_index.for | 48, 108 |
| abstract_inverted_index.has | 55, 103, 116, 144, 154 |
| abstract_inverted_index.how | 80 |
| abstract_inverted_index.k)$ | 107 |
| abstract_inverted_index.n)$ | 149, 164 |
| abstract_inverted_index.the | 20, 29, 42, 49, 62, 65, 84, 88, 91, 96, 99, 109, 124, 133, 142, 167 |
| abstract_inverted_index.also | 78, 94 |
| abstract_inverted_index.each | 10 |
| abstract_inverted_index.k)$, | 58 |
| abstract_inverted_index.rank | 63 |
| abstract_inverted_index.runs | 137 |
| abstract_inverted_index.show | 79 |
| abstract_inverted_index.than | 41 |
| abstract_inverted_index.this | 16 |
| abstract_inverted_index.with | 33 |
| abstract_inverted_index.$k$th | 100 |
| abstract_inverted_index.array | 54 |
| abstract_inverted_index.i.e., | 31 |
| abstract_inverted_index.input | 43 |
| abstract_inverted_index.other | 40 |
| abstract_inverted_index.prove | 95 |
| abstract_inverted_index.query | 66 |
| abstract_inverted_index.where | 59, 121 |
| abstract_inverted_index.$\INV$ | 122 |
| abstract_inverted_index.$f(n)$ | 8 |
| abstract_inverted_index.array. | 92 |
| abstract_inverted_index.input, | 30 |
| abstract_inverted_index.median | 143 |
| abstract_inverted_index.number | 125, 134, 168 |
| abstract_inverted_index.paper, | 17 |
| abstract_inverted_index.reduce | 83 |
| abstract_inverted_index.sorted | 53 |
| abstract_inverted_index.$\RUNS$ | 131 |
| abstract_inverted_index.element | 102, 110, 115 |
| abstract_inverted_index.explore | 19 |
| abstract_inverted_index.finding | 141 |
| abstract_inverted_index.fragile | 1, 21, 35, 56, 86, 105, 117, 145, 155 |
| abstract_inverted_index.minimum | 114 |
| abstract_inverted_index.sorting | 153 |
| abstract_inverted_index.(\INV))$ | 158 |
| abstract_inverted_index.\log\log | 148 |
| abstract_inverted_index.adaptive | 25 |
| abstract_inverted_index.element, | 67 |
| abstract_inverted_index.elements | 89 |
| abstract_inverted_index.expected | 104 |
| abstract_inverted_index.quantity | 39 |
| abstract_inverted_index.setting. | 74 |
| abstract_inverted_index.smallest | 101 |
| abstract_inverted_index.$O(f(n))$ | 14 |
| abstract_inverted_index.algorithm | 6 |
| abstract_inverted_index.amortized | 85 |
| abstract_inverted_index.following | 97 |
| abstract_inverted_index.optimally | 82 |
| abstract_inverted_index.searching | 47 |
| abstract_inverted_index.selected. | 111 |
| abstract_inverted_index.size~$n$. | 44 |
| abstract_inverted_index.algorithms | 24, 32 |
| abstract_inverted_index.complexity | 2, 22, 118, 156, 162 |
| abstract_inverted_index.increasing | 136 |
| abstract_inverted_index.inversions | 127 |
| abstract_inverted_index.randomized | 70 |
| abstract_inverted_index.regardless | 165 |
| abstract_inverted_index.runs.<br/> | 170 |
| abstract_inverted_index.both<br/>in | 68 |
| abstract_inverted_index.predecessor | 50 |
| abstract_inverted_index.$\Theta(\log | 151, 157, 163 |
| abstract_inverted_index.participates | 12 |
| abstract_inverted_index.restrictions | 27 |
| abstract_inverted_index.deterministic | 73 |
| abstract_inverted_index.show<br/>that | 46 |
| abstract_inverted_index.a<br/>sequence | 129 |
| abstract_inverted_index.to<br/>various | 26 |
| abstract_inverted_index.finding<br/>the | 113 |
| abstract_inverted_index.has<br/>fragile | 161 |
| abstract_inverted_index.comparison-based | 5 |
| abstract_inverted_index.Deterministically | 112 |
| abstract_inverted_index.complexity<br/>of | 87 |
| abstract_inverted_index.input<br/>element | 11 |
| abstract_inverted_index.comparisons.<br/>In | 15 |
| abstract_inverted_index.$\Theta(\log(\INV))$ | 119 |
| abstract_inverted_index.results:<br/>Selecting | 98 |
| abstract_inverted_index.predecessor<br/>searches, | 76 |
| abstract_inverted_index.complexity<br/>$O(\log\log | 106 |
| abstract_inverted_index.(\INV))$.<br/>Deterministic | 152 |
| abstract_inverted_index.complexity<br/>$\Theta(\log | 57 |
| abstract_inverted_index.complexity<br/>parameterized | 36 |
| abstract_inverted_index.complexity<br/>$O(\log(\RUNS) | 146 |
| abstract_inverted_index.and<br/>$\Theta(\log(\RUNS))$, | 120 |
| abstract_inverted_index.sequence.<br/>Deterministically | 140 |
| cited_by_percentile_year.max | 93 |
| cited_by_percentile_year.min | 89 |
| corresponding_author_ids | https://openalex.org/A5035971199, https://openalex.org/A5021765002 |
| countries_distinct_count | 4 |
| institutions_distinct_count | 6 |
| corresponding_institution_ids | https://openalex.org/I132053463, https://openalex.org/I177969490 |
| citation_normalized_percentile.value | 0.02641549 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |