Dynamic Optimality Conjecture for splay trees

ghosh.debasish_at_gmail.com
Date: 03/07/05 

Date: 7 Mar 2005 01:35:26 -0800

Dear All -

Splay trees are said to be log(n) competitive for dynamic optimality.
Can anyone please explain why this is said so. AFAIK splay trees are
1-competitive for static optimality and has an online upper bound of
O(mlogn) for most access sequences.

Any help will be appreciated.

- Debasish

Relevant Pages