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).
| Place of Publication | Copenhagen |
|---|
| Publisher | IT-Universitetet i København |
|---|
| Edition | TR-2001-9 |
|---|
| Number of pages | 8 |
|---|
| ISBN (Electronic) | 87-7949-012-3 |
|---|
| Publication status | Published - Nov 2001 |
|---|
| Externally published | Yes |
|---|
| Series | IT University Technical Report Series |
|---|
| Number | TR-2001-9 |
|---|
| ISSN | 1600-6100 |
|---|