Complexity of Data Structures

Gerth Stølting Brodal

Progress report, Department of Computer Science, Aarhus University, Denmark, 29 pages, November 1994.

Abstract

This progress report presents the work accomplished by the author during part A of the Ph.D. programme at the University of Aarhus.

We consider the complexity of different data structures, and introduce the distinction between query and restructuring complexity of data structures. In the light of three different computational frameworks we argue that data structures should be designed to have minimal restructuring complexity.

The main result is the result of [3] where we show how to make bounded degree data structures partially persistent with worst case slowdown in O(1). We also give a restricted result for the case of fully persistent data structures.

Reference [3] is appended at the end of the report.

Online version

progress94.pdf (298 Kb)

Slides

progress94.pdf (228 Kb)

BIBTEX entry

@progressreport{progress94,
  author = "Gerth St{\o}lting Brodal",
  month = "November",
  pages = "29",
  school = "Department of Computer Science, Aarhus University, Denmark",
  title = "Complexity of Data Structures",
  year = "1994"
}