Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re^4: Modified Binary Search

by ikegami (Pope)
on Jan 14, 2010 at 23:10 UTC ( #817500=note: print w/replies, xml ) Need Help??


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

Of course the array construction won't add to the time if you don't include it in the code that's timed.

You assume the same list is always searched.

I suppose a more precise analysis is O(log(N) + N/M) where M is the number of searched performed between modifications of the list. The number of such searches have to be proportional to the size of the list to get less than O(N).

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (3)
As of 2021-06-20 07:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What does the "s" stand for in "perls"? (Whence perls)












    Results (94 votes). Check out past polls.

    Notices?