Maybe time complexity isn't the right term. Performance? There must be some way of describing the efficiency of a program over time.
For instance, I recently had a part of a program that took a continual stream of discrete strings (~256 chars) and checked if each one was in some sort of set or container.
Initially I was using a hash set, though I found despite the O(1) of looking up in the set, computing of the hash of the strings was slower than using a tree instead of a hashset and not computing any hashes.
How would one compare these two operations?
k = key length (smallish, 256) n = items in the collection (~10) m = number of keys streamed (-> infinity) hash set/table lookup: worst: O(m * (k + n)) -> O(m) best: O(m * k) -> O(m) tree lookup: worst: O(m * k) -> O(m) best: O(m)
Usually, in practice, the tree will destroy the hash set. The last time I had to write something like this, the tree lookup was about 5x faster.