Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re^9: Modified Binary Search

by JavaFan (Canon)
on Jan 16, 2010 at 11:36 UTC ( #817755=note: print w/replies, xml ) Need Help??


in reply to Re^8: Modified Binary Search
in thread Modified Binary Search

A well implemented binary search is O(logN) worst case, but averages O(logN - 1).
That's wrong on multiple levels. First of all, your notation is sloppy. O(log N) and O(log N - 1) are equivalent classes. Any function that is in one class is also in the other.

I assume you mean that on average, a well implemented binary search only needs log N - 1 comparisons on average. But that's not true either. That's only true if you only search for elements that are present. Each unsuccessful search will take ceil(log N) or floor(log N) comparisons.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://817755]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (4)
As of 2021-07-28 11:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?