Hashtable question

[JohnGoogle@hotmail.co.uk]

Hi,

I've been reading the documentation for Hashtables and I've come across
the following expressions:

This method is an O(1) operation.
This method is an O(n) operation.

What do these mean?

TIA,

John.

[LoveWiz@gmail.com]

Re: Hashtable question

Hi

Here are cool reference.

http://en.wikipedia.org/wiki/Big_O_notation

Sung Chul, Park

JohnGoogle@hotm ail.co.uk wrote:

Hi,
>
I've been reading the documentation for Hashtables and I've come across
the following expressions:
>
This method is an O(1) operation.
This method is an O(n) operation.
>
What do these mean?
>
TIA,
>
John.

[Bill Butler]

Re: Hashtable question


<JohnGoogle@hot mail.co.ukwrote in message
news:1162772776 .660998.19120@f 16g2000cwb.goog legroups.com...
<snip>

This method is an O(1) operation.
This method is an O(n) operation.
>
What do these mean?

If memory serves correctly the O stands for 'Order'.
Thus O(n) would be called "Order n" and O(n^2) would be "Order n
squared".
This is a measure of how efficient a given algorithm performs.
Technically it is a measure of the asymptotic behavior as the number of
elements gets very large, but, it often is appropriate even for fairly
small collections.

O(1) means that this operation takes a constant amount of time
independent of the number of items involved. A hashtable retrieval is an
O(1) operation

O(n) means that an operation takes a time proportional to the number of
elements (n). If an collection has twice as many elements, the operation
takes twice as long. A linear search is an O(n) operation

others include
O(n^2) : Goes as n*n (not very efficient for large collections)
O(log(n)): goes as the logarithm of the number of elements
O(n*log(n)) : you get the idea.

Hope this helps
Bill

[JohnGoogle@hotmail.co.uk]

Re: Hashtable question

Thanks Bill and poster #2. It makes sense.