Notations

In the tables, if X is a set, we use X as a shortcut for |X| and c for $\vert c(q)\vert, q \in Q$. Space complexity is expressed in bytes and $\sigma$ (resp. q) stands for the number of bytes needed to designate an element of $\Sigma$ (resp. Q). p is the size of a pointer. Values between braces designate time complexity when reallocation is needed.

   

$$Q \Sigma q$$ Matrix

$$\Delta (\sigma + 4p) + 3pQ$$ Map Adjacency List

$$\Delta (\sigma + q)$$ Compact

$$\Delta (\sigma + 2q)$$ Hash Table

$$\Delta (2p + \sigma)$$ Arrays with Binary Search

$$\Delta (2p + \sigma)$$ Arrays with Move-To-Front

$$\Delta (2p + \sigma)$$ Arrays with Transpose

Space complexities of automaton containers

 

1 (Q) 1 No 1 1 1

$$\Delta$$ 1 log c No c c

1 log c 1 1 log c c

Time complexities of automaton containers