Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

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.


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?

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

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (7)
As of 2015-11-29 13:43 GMT
Find Nodes?
    Voting Booth?

    What would be the most significant thing to happen if a rope (or wire) tied the Earth and the Moon together?

    Results (751 votes), past polls