Karpinski (Approximate OBST Optimal Binary Search Trees)
Jump to navigation
Jump to search
Time Complexity
$O(n^{0.6})$
Space Complexity
$O({1})$
(Derived: dynamic programming and making use of Monge matrix properties)
Description
Approximate?
Approximate
Approximation Factor: \epsilon = o(1)
Randomized?
No, deterministic
Model of Computation
Year
1996
Reference
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.6940&rep=rep1&type=pdf