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):
https://books.google.com/books?id=eErBDwAAQBAJ&pg=PA307&lpg=PA307&dq=bfs+time+complexity+elements+of+programming+interviews+18.7&source=bl&ots=Fotetv7x03&sig=ACfU3U1xyJkEMT7Y69cREXJvOrz9bRw4pw&hl=en&sa=X&ved=2ahUKEwiu48TS98fpAhWNsp4KHZF2BS4Q6AEwAHoECAoQAQ#v=onepage&q=bfs%20time%20complexity%20elements%20of%20programming%20interviews%2018.7&f=false
The number of vertices is d, the number of words in the dictionary. The number of edges is, in the worst-case O(d²). The time complexity is that of BFS, namely O(d+d²) = O(d²). 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². We know that the complexity of BFS is O(V+E), hence O(d+d²) = O(d²), though if we used a set to record visited verices (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. 923
If the string length n is less than d the maximum number of edges out of a vertex is O(n). I don't agree with this. Imagine we have 5 words in our dictionary {ab, ac, ad, ae, af}, so d is 5 and n is 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 from 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 :) 180