previousnext
ASTL homeSTL home
   
Complexities and DFAs


Notations

Concerning complexities, if X is a set, we write X as a shortcut for |X| an c for |c(q)|, q in Q. Space complexity is an approximation and is expressed in bytes, stands for the number of bytes needed to code an element of , p is the size of a pointer and t is the size of a user-defined tag.

Table

Matrix Adj. List Compact Bin. search Array mtf Array tr
Insert state
am. 1
1
NO
1
1
1
delete state
1
1
NO
1
1
1
Insert trans
1
log2(c)
NO
c+log2(c)
am. 1
am. 1
Delete trans
1
log2(c)
NO
c+log2(c)
c
c
Access trans
1
log2(c)
1
log2(c)
c
c
Iter edges
c
c
c
c
Space