Dynamic Nested Brackets
- Stephen Alstrup,
- Theis Rauhe,
- Lund University
Research Output:
Book / Anthology / Report
Report
Open access
Publication Information
Output type
Research Output:
Book / Anthology / Report
Report
Original language
EnglishPublication milestones
- Published - 11/2001
Publication status
Published - 11/2001
Place of publication
CopenhagenEdition
TR-2001-9Publisher
IT-Universitetet i København, DenmarkBook series
- Book series name: IT University Technical Report Series
Series number: TR-2001-9
ISSN: 1600-6100
ISBN (Electronic)
87-7949-012-3Abstract
We consider the problem of maintaining a string of brackets like (()(()))of length n under a single operation reverse(i). The operation reverse(i) changes the the letter from '(' to) ` ' or vice versa, and returns `yes' if and only if the updated string is balanced.
We give lower and upper bounds showing that the complexity of reverse(i) is (-)(log n/loglog n).
We give lower and upper bounds showing that the complexity of reverse(i) is (-)(log n/loglog n).
Access to documents
Final published version, 84.65 KB