What is the time complexity of lookups in directed acyclic word graphs?

A directed acyclic word graph is a great data structure for certain tasks. I can't开发者_如何学Python find any information on the time complexity of performing a lookup though.

I would guess it depends linearly on the average word length, and logarithmically on the number of words in the graph.

So is it O(L * log W), where W is the number of words and L is the average word length?

I think that complexity is just O(L). Number of operations is proportional to length of word and it does not matter how many entries structure have. (there might be differences based on implementation of node searching but that is in worst case and worst implementation just constant whit upper limit equal to size of alphabet)

I’d say it’s just O(L). For each lookup of a word of n characters, you always follow at most n edges, irrespective of how many other edges there are.

(That’s assuming a standard DAWG in which each node has outgoing edges for every letter of the alphabet, i.e. 26 for English. Even if you have fewer outgoing edges per node and therefore more levels, the number of edges to follow is still at most a constant multiple of n, so we still get O(L).)

How many words you already have in your structure seems to be irrelevant.

Even if, at each step, you perform a linear search for the correct edge to follow from the current node, this is still constant-time because the alphabet is bounded, and therefore so is the number of outgoing edges from each node.