CODEWITHSUNDEEP
c#hashtabletime-complexity
Sciphi
Sciphi

Reputation: 13

C# hashtable classes lookup by key is O(1)?

I read up on "Big O" and thought of the above. Is it correct ... ?

Answer (provided by @Mehrdad below): worst case is O(n)

Edit: sorry I meant 0(1), thanks @Coxy corrected that too.

Upvotes: 1

Views: 3684

Answers (1)

user541686
user541686

Reputation: 210352

Yeah, it's O(1), or constant-time.

We say that the lookup is on the order of 1, or, in math notation, O(1). This means that, in the worst case, the lookup takes constant time*, irrespective of the data.

This is amortized worst-case time -- you might want to look this up, but basically, it means that, when spread out over the life of your hashtable, the cost is constant. The actual worst-case time may be different than here, depending on how you make the buckets in the hashtable -- it can actually be anywhere from O(1) to O(n), but the theoretical best is O(1) as I wrote here.

Another note: I'm actually a bit sloppy with the notation myself: to really do it correctly requires set notation.

Upvotes: 1

Related Questions