Balanced trees

Marko Rauhamaa marko at pacujo.net
Mon Mar 10 07:16:43 CET 2014


Steven D'Aprano <steve+comp.lang.python at pearwood.info>:

> Proof: I create a hash table that accepts unsigned bytes as keys, where 

The O(f(n)) notation has no meaning when n is limited.

This thing is not just pedantry. The discussion was how a balanced tree
fares in comparison with hash tables. A simplistic O(1) vs O(log n) was
presented as a proof that balanced trees don't have a chance in practice
or theory. I wasn't so easily convinced.


Marko



More information about the Python-list mailing list