Robert Tarjan is a computer scientist whose work connects efficient graph algorithms, data structures and rigorous analysis. His contributions include algorithms for lowest common ancestors and, with collaborators, splay trees and Fibonacci heaps.[ref]
His work on amortized analysis explains why an individual operation can be expensive while a whole sequence remains efficient. The accounting assigns the cost of occasional restructuring across the sequence instead of assuming each operation has the same worst-case cost. Splay trees make this distinction particularly concrete: moving recently accessed nodes changes the tree while supporting strong bounds over a sequence of accesses.[ref]
Amortized Computational Complexity by Robert Endre Tarjan. Sections 1–2, total sequence cost and amortization
Homepage: www.cs.princeton.edu/~ret/
Institutional profile: www.hertzfoundation.org/people/robert-tarjan/
Articles by others on the same topic
Robert Tarjan is a prominent American computer scientist known for his contributions to algorithms and data structures. He was born on July 30, 1948. Tarjan is particularly noted for his work on graph algorithms, including the development of efficient algorithms for network flow problems, the analysis of data structures such as disjoint-set (union-find), and the discovery of the concept of "strongly connected components" in directed graphs.