Which Big-O equation describes my search?
I have a sorted array of doubles (actually actually) that are relatively evenly spaced in the -10 to -43 range. Now if I do a binary search on this list, I get O (log N).
But I can further optimize the search by having a lookup table where I have 34 keys (-10 to -43), which can then go straight to the starting point of that number.
For example: -23.123424 first find the key 23 and find out the initial range of all values -23. Then I can do a binary search from the middle of that.
What would my Big-O look like?
source to share
It's still O (log n). Consider: it takes constant time to find the starting indices in the integer table, so the part adds nothing. Then O (log n) does a binary search. In fact, it will take roughly log n / 34 because you would expect 34 times less on average (values are distributed over 34 different intervals ranging from -43 to -10), but constant factors do not count towards large -Os.
source to share
It will still be O(log N)
, but for a smaller dataset (think a smaller value for N).
Since the lookup table provides ca. 1/34, which is close to 1/32 or 5 steps in binary search, you might want to compare if it really helps: extra code paths with a lot of cache misses and one or the other misprediction / cleanup pipeline can make it slower. than direct binary search.
Also, if lookup time for an in-memory table is a bottleneck, you might want to consider representing your lats as values Int32
- definitely accurate enough, but much faster to look up.
source to share
It looks like your optimization will help, but I think it still counts as O (log N) because you still need to look for the exact value. If you took yourself directly to the value, it would be O (1)
This is a limitation for Big-Oh analysis. This does not take into account that you have reduced the number of values you should be looking for.
source to share
Your concept is close to that of interpolation search , except that instead of "interpolating" once on an integral part of the key, it recursively uses interpolation to intelligently control the binary search. Since your domain is relatively homogeneous, the expected uptime is O(log log n)
.
source to share