How to describe the time complexity of a continually running program with a stream of inputs?

Question

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.

Answer 1

I would say that you should not look at the overall runtime (as it will be dominated by $m =\infty$ anyway) and instead look at the expected complexity of processing a single element (or a group of them if it doesn't scale linearly).

I'm not entirely sure what you mean with "Tree lookup" but I will just guess and provide an answer for that:

Calculating the hash of a key with length $k$ is done in $\mathcal O(k)$. The corresponding field in the hashmap/table/set is then retrieved with a single lookup.

Assuming your tree is a BST where each node is a key (256 chars, alphabet of size 26) and you compare either left or right side and you have 10 nodes in the tree:

• The tree has $log_2(10) \approx 4$ levels (1,2,4,2 nodes)
• For a lookup, in each level the current key has to be compared to the node's key. The chance that the first characters match is $\frac1{26}$. That the first two match $\frac1{26^2}$, and so on.
• In most cases, you will have a mismatch at the all four nodes where a value is compared
• Your average case thus involves a few (2-4) lookups (following left or right child pointers in the tree) and comparing a few letters. If the key matches, the whole key is compared but I assume that this doesn't happen very often.

Thus, the BST lookup has a better performance without further modifications.

Maybe more fitting for stackoverflow than cs.stackexchange but still, my suggestion for your problem would be the following:

• Determine if the values in the collection have some pattern (if they are SHA hashes of random data or similar, very very likely not the case)
• Look at the percentage of successful matches (I would guess very low)
• Implement a custom "Hashing". If the items in your collections start with different letters (or 2, whatever), you only need the first letter of each element in your stream to know with which item from your collection you have to compare it (for equality).