Dynamic optimality - Almost

Erik D. Demaine, Dion Harmon, John Iacono, Mihai Pǎtraşcu

    Research output: Contribution to journalArticle

    Abstract

    We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan's dynamic optimality conjecture of 1985 that O(1 )-competitive binary search trees exist.

    Original languageEnglish (US)
    Pages (from-to)240-251
    Number of pages12
    JournalSIAM Journal on Computing
    Volume37
    Issue number1
    DOIs
    StatePublished - 2007

    Keywords

    • Binary search trees
    • Competitiveness
    • Splay trees

    ASJC Scopus subject areas

    • Computer Science(all)
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Dynamic optimality - Almost'. Together they form a unique fingerprint.

  • Cite this

    Demaine, E. D., Harmon, D., Iacono, J., & Pǎtraşcu, M. (2007). Dynamic optimality - Almost. SIAM Journal on Computing, 37(1), 240-251. https://doi.org/10.1137/S0097539705447347