6 Mar
2008
6 Mar
'08
5:48 p.m.
Johannes Waldmann wrote:
I learned at school, and I teach my students, * balanced binary tree: costs are log(size) * hashtable: costs are essentially constant
Correction: * hashtable: costs are key size in bits which is always >= log(size) (because: pigeonhole principle) (The size being the number of elements stored, not a preallocated table size. But those two should be proportional anyway.) So, hash tables have no asymptotic benefits, it's all in the constant factors. Regards, apfelmus