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