|Presentation for Open Source Project: lcalibrary|
With some simple dynamic programming we can turn the O(n^3) into an O(n^2) but that is still not good enough.
We want the fastest solution possible, in fact, a solution that runs in
linear time would be best. Our goal is to preprocess our dataset in O(n) to
provide O(1) lookups.
Copyright 2003, Zack Ramjan