Editing In-place algorithm (section)

== In computational complexity ==
{{See also|SL (complexity)}}
In [[computational complexity theory]], the strict definition of in-place algorithms includes all algorithms with {{math|''O''(1)}} space complexity, the class '''[[Deterministic space|DSPACE]]'''(1). This class is very limited; it equals the [[regular language]]s.<ref>Maciej Liśkiewicz and Rüdiger Reischuk. [http://citeseer.ist.psu.edu/34203.html The Complexity World below Logarithmic Space]. ''Structure in Complexity Theory Conference'', pp. 64–78. 1994. Online: p. 3, Theorem 2.</ref> In fact, it does not even include any of the examples listed above.

Algorithms are usually considered in [[L (complexity)|L]], the class of problems requiring {{math|''O''(log ''n'')}} additional space, to be in-place. This class is more in line with the practical definition, as it allows numbers of size {{math|''n''}} as pointers or indices. This expanded definition still excludes quicksort, however, because of its recursive calls.  

Identifying the in-place algorithms with L has some interesting implications; for example, it means that there is a (rather complex) in-place algorithm to determine whether a path exists between two nodes in an [[undirected graph]],<ref>{{citation
 | last = Reingold | first = Omer | author-link = Omer Reingold
 | doi = 10.1145/1391289.1391291
 | issue = 4
 | id = {{ECCC|2004|04|094}}
 | journal = [[Journal of the ACM]]
 | mr = 2445014
 | pages = 1–24
 | title = Undirected connectivity in log-space
 | volume = 55
 | year = 2008| s2cid = 207168478 }}</ref> a problem that requires {{math|''O''(''n'')}} extra space using typical algorithms such as [[depth-first search]] (a visited bit for each node). This in turn yields in-place algorithms for problems such as determining if a graph is [[bipartite graph|bipartite]] or testing whether two graphs have the same number of [[connected component (graph theory)|connected component]]s.