BFS complexity Why is the complexity


I’m having a hard time understand the reasoning in the solution of 18.7 in Elements of programming interviews (EPI):

Let $ s$ and $ t$ be stings and $ D$ a dictionary, i.e., a set of strings. Define $ s$ to produce $ t$ if there exists a sequence of strings from the dictionary $ P = \langle s_0,s_1,\ldots,s_{n-1} \rangle$ such that the first string is $ s$ , the last string is $ t$ , and adjacent strings have the same length and differ in exactly one character. The sequence $ P$ is called a production sequence. For example, if the dictionary is {bat,cot,dog,dag,dot,cat}, then ⟨cat,cot,dot,dog⟩ is a valid production sequence.

Given a dictionary $ D$ and two strings $ s$ and $ t$ , write a program to determine if $ s$ produces $ t$ . Assume that all characters are lowercase alphabets. If $ s$ does produce $ t$ , output the length of a shortest production sequence; otherwise, output -1.

Hint: Treat strings as vertices in an undirected graph, with an edge between $ u$ and $ v$ if and only if the corresponding strings differ in one character.

Here is the solution:

The number of vertices is $ d$ , the number of words in the dictionary. The number of edges is, in the worst-case $ O(d^2)$ . The time complexity is that of BFS, namely $ O(d+d^2) = O(d^2)$ . If the string length $ n$ is less than $ d$ then the maximum number of edges out of a vertex is $ O(n)$ , implying an $ O(nd)$ bound.

So I agree with number of vertices being $ d$ , and the worst case number of edges is $ d^2$ . We know that the complexity of BFS is $ O(V+E)$ , hence $ O(d+d^2) = O(d^2)$ , though if we used a set to record visited vertices (or removed a vertex once we visited it from the graph), that should reduce BFS’s complexity to $ O(d)$ . But then things get funky.

If the string length $ n$ is less than $ d$ then the maximum number of edges out of a vertex is $ O(n)$ .

don’t agree with this. Imagine we have 5 words in our dictionary $ \{ab, ac, ad, ae, af\}$ , so $ d=5$ and $ n=2$ . All these vertices are connected and you can see that each vertex has 4 edges leaving it… which is more than $ O(n)$ . You can have $ 26^n$ possible edges leaving the vertex, but you only have $ d$ vertices in the graph, so the number of edges leaving a single vertex should be $ O(d)$ .

I ultimately agree that the final complexity of the algorithm is $ O(nd)$ , but I calculated that simply given that we can visit up to $ d$ vertices (we use a visited set to prevent cycles) and for each vertex visited one we iterate over the string of length $ n$ as we look for differences in the alphabet of lower characters $ O(26nd) = O(nd$ ).

Interested to hear what people think, Thanks 🙂