Talk:Hash table

may I ask what is O(1)? Robert Tito | Talk 14:39, 21 February 2007 (CST)

The O(n)-notation gives a hint on the complexity of a task, i.e. on the computational time needed to perform the task. n is the number of elements in consideration. This means if a task is in O(n) class, the time to perform the task increases linearly with the number of elements. O(1) (what you asked for) means that the time does not increase with the number of elements. O(n^2) would mean that time grows quadratically with the number of elements. Typical classe are O(1), O(log n), O(n), O(n log n), O(n2) and O(2^n). -- Alexander Wiebel 15:08, 21 February 2007 (CST)

By the way, this belongs to the field of theoretical computer science. Hope that helps. -- Alexander Wiebel 15:10, 21 February 2007 (CST)

I was hoping to come in later and write the article 'Big O Notation,' which would have cleared this up. As a general style rule, should I explain that in the article text instead of just linking to Big O Notation? --Nick Johnson 15:57, 21 February 2007 (CST)

understanding

See my remark as Alexander Wiebel's page:

order

To indicate an order, not the O is used but a curly O, ϑ though that is the theta. In a definition it seems inappropriate to state the order of what is meant. I guessed Order was meant but then it leaves me wondering: order of what in what. I hope you can understand this argument. Robert Tito | Talk 15:15, 21 February 2007 (CST) May I suggest to remove the Order from the definition and explain it in the article?Robert Tito | Talk 16:10, 21 February 2007 (CST)

I've seen the notation ${\mathcal {O}}(n)$, but only rarely. It may be a bit strong to say that $O(n)$ is incorrect. Greg Woodhouse 13:00, 30 April 2007 (CDT)

I do not see its contribution to hash tables at all, I would suggest removing the O(n) and replacing it by complexity ≈ n, or n^2. stating that the time needed to sort is proportional to the number of elements, or to its square or root or whatever is appropriate. To me that seems to make more sense than using some obscure order function that has no definition. Of course an explanation about the proportionality is appropriate. Robert Tito |  Talk  13:26, 30 April 2007 (CDT)

You'll get no argument from me there. The confusion is that if fixed size keys are used, it is reasonable to say that the hash algorithm should run in constant time (which is all that O(1) means), but the algorithms won't really run in constant time, it's just that a fixed key size makes it effectively constant. Greg Woodhouse 13:40, 30 April 2007 (CDT)