# Splay Trees - Sequential Access Theorem & lower bound for comparison-based sorting

The following theorem was proven by R.E. Tarjan in 1984:

Theorem (Sequential Access Theorem). If we access each of the nodes of an arbitrary initial tree once, in symmetric order, the total time spent is $$O(n)$$

But if we remove the smallest element one at a time, then does it imply that we sorted the element in $$O(n)$$ time? Of course not, because then it contradicts the following Theorem.

Any comparison sort algorithm requires $$\Omega(n\lg n)$$ comparisons in the worst case.

What was wrong with the way I tried to use the Sequential Access Theorem?

There is nothing wrong in saying that if you access the nodes of a BST (not necessarily a splay tree) in symmetric order in time $$O(n)$$ then the sequence of the corresponding elements is sorted.
However this alone is not enough to obtain a sorting algorithm that runs in time $$O(n)$$ since you're disregarding the time needed to construct the tree itself.
In fact, your observation shows that the time spent to build a BST from an unsorted set of elements must be $$\Omega(n \log n)$$ in the worst case.