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 userdefined 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 





