Comment by ant6n 8 years ago I thought a hash table has O(n) access. 4 comments ant6n Reply bufferoverflow 8 years ago Average O(1), worst case O(n)So worse than a B-tree or a Red-black tree for the worst case. ant6n 8 years ago "Average O(1)" is an oxymoron. Big Oh is about the worst case. The only thing that makes sense is "Amortized O(1)", but I believe its possible to create access cases where hash tables are slower. zzzcpan 8 years ago Only some primitive hash table algorithms have O(n) worst case access. No one implements those algorithms anymore though. IncRnd 8 years ago Big-O specifically refers to worst case, though, people use Big-O to refer to average or worst case scale in-practice.
bufferoverflow 8 years ago Average O(1), worst case O(n)So worse than a B-tree or a Red-black tree for the worst case. ant6n 8 years ago "Average O(1)" is an oxymoron. Big Oh is about the worst case. The only thing that makes sense is "Amortized O(1)", but I believe its possible to create access cases where hash tables are slower.
ant6n 8 years ago "Average O(1)" is an oxymoron. Big Oh is about the worst case. The only thing that makes sense is "Amortized O(1)", but I believe its possible to create access cases where hash tables are slower.
zzzcpan 8 years ago Only some primitive hash table algorithms have O(n) worst case access. No one implements those algorithms anymore though.
IncRnd 8 years ago Big-O specifically refers to worst case, though, people use Big-O to refer to average or worst case scale in-practice.
Average O(1), worst case O(n)
So worse than a B-tree or a Red-black tree for the worst case.
"Average O(1)" is an oxymoron. Big Oh is about the worst case. The only thing that makes sense is "Amortized O(1)", but I believe its possible to create access cases where hash tables are slower.
Only some primitive hash table algorithms have O(n) worst case access. No one implements those algorithms anymore though.
Big-O specifically refers to worst case, though, people use Big-O to refer to average or worst case scale in-practice.