Concepedia

Search Complexity Analysis

Search Complexity Analysis is a theoretical framework within algorithmic analysis that characterizes the efficiency of search operations in data structures, particularly probabilistic hierarchical structures like skip lists, by quantifying the expected number of comparisons and pointer traversals required to locate an element as a function of input size.

344

Publications

19K

Citations

682

Authors

349

Institutions

Publications per year

2017–2026

29

Parents

Publications

344

A fast string searching algorithm

Robert S. Boyer, J Strother Moore · Communications of the ACM · 1977 · 2.3K citations · Full text

, , +9

Analytic and Algorithmic Solution of Random Satisfiability Problems

Marc Mézard, Giorgio Parisi, Riccardo Zecchina · Science · 2002 · 1.1K citations · Full text

, , +17

A fast algorithm for finding dominators in a flowgraph

Thomas Lengauer, Robert E. Tarjan · ACM Transactions on Programming Languages and Systems · 1979 · 632 citations

, , +12

Sequential Coding Algorithms: A Survey and Cost Analysis

J. Anderson, Seshadri Mohan · IRE Transactions on Communications Systems · 1984 · 548 citations

, , +16

The complexity of logic-based abduction

Thomas Eiter, Georg Gottlob · Journal of the ACM · 1995 · 428 citations · Full text

, , +15

1–5 of 344

Authors

682

  1. RE
    Richard E. Korf

    University of California, Los Angeles, United States

    6 publications · 259 citations

    6

    h-index

  2. MT
    Mikkel Thorup

    AT&T (United States), United States

    5 publications · 328 citations

    5

    h-index

  3. AA
    Arne Andersson

    Uppsala University, Sweden

    5 publications · 164 citations

    5

    h-index

  4. WR
    Wheeler Ruml

    University of New Hampshire at Manchester, United States

    4 publications · 114 citations

    4

    h-index

  5. JS
    Jonathan Schaeffer

    University of Alberta, Canada

    4 publications · 326 citations

    4

    h-index

1–5 of 682

Institutions

349

  1. University of California, Los Angeles

    Los Angeles, United States

    10 h-index

    14 publications

    703 citations

  2. University of Waterloo

    Waterloo, Canada

    8 h-index

    15 publications

    517 citations

  3. University of Alberta

    Edmonton, Canada

    7 h-index

    21 publications

    1.6K citations

  4. AT&T (United States)

    Bedminster, United States

    6 h-index

    6 publications

    433 citations

  5. Massachusetts Institute of Technology

    Cambridge, United States

    6 h-index

    10 publications

    586 citations

  6. Princeton University

    Princeton, United States

    6 h-index

    7 publications

    300 citations

  7. Carnegie Mellon University

    Pittsburgh, United States

    6 h-index

    9 publications

    290 citations

  8. University of Chile

    Santiago, Chile

    5 h-index

    7 publications

    307 citations

1–8 of 349

Venues

  1. SIAM Journal on Computing

    11 publications · 781 citations

    11

    h-index

  2. Journal of the ACM

    JACM · 12 publications · 1.2K citations

    11

    h-index

  3. Theoretical Computer Science

    9 publications · 418 citations

    9

    h-index

  4. Information Processing Letters

    8 publications · 551 citations

    8

    h-index

  5. Symposium on Discrete Algorithms

    Conference · 5 publications · 113 citations

    5

    h-index

1–5