Aho, Hopcroft, and Ullman (Offline) (Off-Line Lowest Common Ancestor Lowest Common Ancestor)

Time Complexity

$O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function

Space Complexity

$O(n)$ words

(https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1976

Reference

https://dl.acm.org/doi/pdf/10.1145/800125.804056