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).
Udgivelsessted | Copenhagen |
---|
Forlag | IT-Universitetet i København |
---|
Udgave | TR-2001-9 |
---|
Antal sider | 8 |
---|
ISBN (Elektronisk) | 87-7949-012-3 |
---|
Status | Udgivet - nov. 2001 |
---|
Udgivet eksternt | Ja |
---|
Navn | IT University Technical Report Series |
---|
Nummer | TR-2001-9 |
---|
ISSN | 1600-6100 |
---|