Larmore (Approximate OBST Optimal Binary Search Trees)
Jump to navigation
Jump to search
Time Complexity
$O(n^{1.6})$
Space Complexity
$O(n)$
(Derived: Computing and storing f_{d,l} for each n elements)
Description
Approximate?
Approximate
Approximation Factor: \epsilon = o(1)
Randomized?
No, deterministic
Model of Computation
Year
1987
Reference
https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0196677487900526