Recursively rotated orders and implicit data structures: A lower bound

DOI10.1016/0304-3975(84)90013-6zbMath0537.68060OpenAlexW2043343347MaRDI QIDQ792764

Greg N. Frederickson

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90013-6

zbMATH Keywords

lower boundpartial orderdictionaryimplicit data structurerecursively rotated order

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05)

Related Items

A pointer-free data structure for merging heaps and min-max heaps ⋮ An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time

Cites Work

• Implicit data structures for fast search and update
• Recurrence relations based on minimization
• Implicit Data Structures for the Dictionary Problem