access produces better memory access patterns. There are also efficient algorithms to dynamically track the components of a graph as vertices and edges are added, by using a disjoint-set data structure to keep track of the partition of the vertices into equivalence classes, replacing any two classes by their union when an edge connecting them is added. These algorithms take amortized time per operation, where adding vertices and edges and determining the component in which a vertex falls are both operations, and is a very slowly growing inverse of the very quickly growing Ackermann function. One application of this sort of incremental connectivity algorithm is in Kruskal's algorithm for minimum spanning trees, which adds edges to a graph in sorted order by length and includes an edge in the minimum spanning tree only when it connects two different components of the previously-added subgraph. When both edge insertions and edge deletions are allowed, dynamic connectivity algorithms can still maintain the same information, in amortized time per change and time per connectivity query, or in near-logarithmic randomized expected time. Components of graphs have been used in computational complexity theory to study the power of Turing machines that have a working memory limited to a logarithmic number of bits, with the much larger input accessible only through read access rather than being modifiable. The problems that can be solved by machines limited in this way define the complexity class L. It was unclear for many years whether connected components could be found in this model, when formalized as a decision problem of testing whether two vertices belong to the same component, and in 1982 a related complexity class, SL, was defined to include this connectivity problem and any other problem equivalent to it under logarithmic-space reductions. It was finally proven in 2008 that this connectivity problem can be solved in logarithmic space, and therefore that In a graph represented as an adjacency list, with random access to its vertices, it is possible to estimate the number of connected components, with constant probability of obtaining additive (absolute) error at most , in sublinear time . In random graphs In random graphs the sizes of components are given by a random variable, which, in turn, depends on the specific model of how random graphs are chosen. In the version of the Erdős–Rényi–Gilbert model, a graph on vertices is generated by choosing randomly and independently for