# Pointer algorithm

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Pointer_algorithm
> Markdown URL: https://mediated.wiki/source/Pointer_algorithm.md
> Source: https://en.wikipedia.org/wiki/Pointer_algorithm
> Source revision: 1316943286
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [computer science](/source/computer_science), a '''pointer algorithm''' (sometimes called a pointer machine, or a reference machine; see the article
[Pointer machine](/source/Pointer_machine) for a close but non-identical concept) is a type of algorithm that manages a linked data structure.
This concept is used as a model for lower-bound proofs and specific restrictions on the linked data structure and on the algorithm's access to the structure vary. 

This model has been used extensively with problems related to the [disjoint-set data structure](/source/disjoint-set_data_structure). Thus,
[Tarjan](/source/Robert_Endre_Tarjan) and [La Poutré](/source/Johannes_A._La_Poutr%C3%A9) used this model to prove lower bounds on the amortized complexity of a disjoint-set data structure<ref>{{Cite journal
 | last = Tarjan
 | first = Robert E.
 | title = A class of algorithms which require nonlinear time to maintain disjoint sets
 | journal = Journal of Computer and System Sciences
 | volume = 18
 | issue = 2
 | pages = 110–127
 | year = 1979
 | doi = 10.1016/0022-0000(79)90042-4
 | pmid = 
 | url = 
}}</ref><ref>{{Cite book
 | last = La Poutré
 | first = Johannes A.
 | title = Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90
 | chapter = Lower bounds for the union-find and the split-find problem on pointer machines
 | editor = 
 | publisher = ACM
 | location = 
 | pages = 34–44
 | year = 1990
 | url = 
 | doi = 10.1145/100216.100221 |doi-access=free
 | isbn = 0-89791-361-2
}}
* See also {{cite journal |last1=La Poutré |first1=Han |title=Lower Bounds for the Union–Find and the Split–Find Problem on Pointer Machines |journal=Journal of Computer and System Sciences |date=1996 |volume=52 |pages=87–99 |doi=10.1006/jcss.1996.0008}}</ref> (La Poutré also addressed the [interval split-find problem](/source/interval_split-find_problem)). [Blum](/source/Norbert_Blum) used this model to prove a lower bound on the single operation worst-case time of disjoint set data structure.<ref>{{Cite journal
 | last = Blum
 | first = Norbert
 | title = On the single operation worst-case time complexity of the disjoint set union problem
 | journal = SIAM Journal on Computing
 | volume = 15
 | issue = 4
 | pages = 1021–1024
 | year = 1986
 | doi = 10.1137/0215072
 | pmid = 
 | url = 
}}</ref> Blum and [Rochow](/source/Henning_Rochow) proved a worst-case lower bound for the [interval union-find](/source/interval_union-find) problem.<ref>{{Cite journal
 | last1 = Blum
 | first1 = Norbert
 | last2 = Rochow
 | first2 = Henning
 | title = A lower bound on the single operation worst-case time complexity of the union-find problem on intervals
 | journal = Information Processing Letters
 | volume = 51
 | issue = 2
 | pages = 57–60
 | year = 1994
 | doi = 10.1016/0020-0190(94)00082-4
 | pmid = 
 | url = 
}}</ref>

==Example==
In Tarjan's lower bound for the disjoint set union problem, the assumptions on the algorithm are:
* The algorithm maintains a linked structure of nodes.
* Each element of the problem is associated with a node.
* Each set is represented by a node.
* The nodes of each set constitute a distinct connected component in the structure (this property is called ''separability'').
* The '''find''' operation is performed by following links from the element node to the set node.
Under these assumptions, the lower bound of <math>\Omega(m\alpha(m,n))</math> on the cost of a sequence of ''m'' operations is proven.

==References==
{{Reflist}}

Category:Algorithms

---
Adapted from the Wikipedia article [Pointer algorithm](https://en.wikipedia.org/wiki/Pointer_algorithm) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Pointer_algorithm?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.