Recursively rotated orders and implicit data structures: A lower bound

DOI10.1016/0304-3975(84)90013-6MaRDI QIDQ792764zbMATH OpenOpenAlexFDO

Authors 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) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 2079398
• Implicit \(B\)-trees: A new data structure for the dictionary problem
• An implicit data structure supporting insertion, deletion, and search in O( ^ 2\,n) time
• Optimal implicit dictionaries over unbounded universes
• Optimal worst-case operations for implicit cache-oblivious search trees.

Cites work

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

Cited in

(3)

• scientific article; zbMATH DE number 2085285 (Why is no real title available?)
• 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

This page was built for publication: Recursively rotated orders and implicit data structures: A lower bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792764)