Concepedia

Comparison Complexity

Comparison Complexity is a theoretical measure in the analysis of sorting algorithms that quantifies the number of pairwise comparisons required to sort a given set of elements, distinguishing it from other complexity measures by focusing exclusively on comparison operations as the fundamental computational step.

118

Publications

4.9K

Citations

219

Authors

116

Institutions

Publications per year

2017–2026

9

Variants

Comparison-based Complexity

Parents

Publications

118

Parallelism in Comparison Problems

Leslie G. Valiant · SIAM Journal on Computing · 1975 · 401 citations

, , +16

Computing with Noisy Information

Uriel Feige, Prabhakar Raghavan, David Peleg et al. · SIAM Journal on Computing · 1994 · 314 citations

, , +16

Expected time bounds for selection

Robert W. Floyd, Ronald L. Rivest · Communications of the ACM · 1975 · 280 citations · Full text

, , +12

On the sorting-complexity of suffix tree construction

Martı́n Farach-Colton, Paolo Ferragina, S. Muthukrishnan · Journal of the ACM · 2000 · 211 citations · Full text

, , +16

A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets

F. K. Hwang, Shengmao Lin · SIAM Journal on Computing · 1972 · 144 citations

, , +13

1–5 of 118

Authors

219

  1. UZ
    Uri Zwick

    Tel Aviv University, Israel

    6 publications · 181 citations

    6

    h-index

  2. AC
    Andrew Chi-Chih Yao

    Princeton University, United States

    4 publications · 106 citations

    4

    h-index

  3. RC
    Richard Cole

    New York University, United States

    4 publications · 165 citations

    4

    h-index

  4. JA
    James Allen Fill

    Johns Hopkins University, United States

    4 publications · 67 citations

    4

    h-index

  5. RL
    Ronald L. Rivest

    Massachusetts Institute of Technology, United States

    3 publications · 338 citations

    3

    h-index

1–5 of 219

Institutions

116

  1. Johns Hopkins University

    Baltimore, United States

    5 h-index

    7 publications

    119 citations

  2. University of Toronto

    Toronto, Canada

    3 h-index

    3 publications

    83 citations

  3. University of Washington

    Seattle, United States

    3 h-index

    3 publications

    81 citations

  4. New York University

    New York, United States

    3 h-index

    6 publications

    179 citations

  5. University of Pisa

    Pisa, Italy

    3 h-index

    4 publications

    254 citations

  6. Tel Aviv University

    Tel Aviv, Israel

    3 h-index

    5 publications

    107 citations

  7. Princeton University

    Princeton, United States

    3 h-index

    5 publications

    144 citations

  8. Hebrew University of Jerusalem

    Jerusalem, Israel

    2 h-index

    2 publications

    103 citations

1–8 of 116

Venues

  1. SIAM Journal on Computing

    25 publications · 1.9K citations

    20

    h-index

  2. ACM Transactions on Algorithms

    TALG · 5 publications · 184 citations

    5

    h-index

  3. IEEE Transactions on Computers

    4 publications · 119 citations

    4

    h-index

  4. Algorithmica

    4 publications · 82 citations

    4

    h-index

  5. Journal of the ACM

    JACM · 4 publications · 311 citations

    4

    h-index

1–5