Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: Re: An informal introduction to O(N) notation

by Jenda (Abbot)
on Jan 19, 2003 at 17:54 UTC ( #228196=note: print w/ replies, xml ) Need Help??


in reply to Re: An informal introduction to O(N) notation
in thread An informal introduction to O(N) notation

Most often k is not a constant, but a function of n. If for example k would be ~ c * n then the average length of the lists of items in each bucket would be ~ n / (c * n) which is ~ 1 / c. Which is a constant.

Therefore the key lookup of the usual implementations of hashes has average complexity of o(1).

Of course this implementation forces you to recreate the hash when the number of keys grows over some limit which can be time consuming.

Jenda

P.S.: I just looked at the number of buckets in the Perl hashes (I iteratively added elements, watched the number of buckets and printed the number of elements and buckets after every rehashing). This is the results:

1 => 8 9 => 16 18 => 32 34 => 64 70 => 128 130 => 256 258 => 512 514 => 1024 1024 => 2048 2052 => 4096 4098 => 8192 8193 => 16384 16386 => 32768 32768 => 65536 65538 => 131072 Perl 5.8.0 built for MSWin32-x86-multi-thread


Comment on Re: Re: An informal introduction to O(N) notation
Select or Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (3)
As of 2014-10-25 00:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (138 votes), past polls