1

i dont understand how the following complexities come from.

espeacialy b(b^d-1) in the time complexity

Time complexity: Total numb. of nodes generated: 1 + b + b2 + … + bd + b(b^d-1) = O(b^(d+1)) Space complexity:O(b^(d+1))

where b – maximum branching factor of the search tree d – depth of the least-cost solution

James McNellis
  • 348,265
  • 75
  • 913
  • 977
ms.twenty four
  • 31
  • 1
  • 2
  • 3

3 Answers3

3

In simpler terms in BFS we make use of a queue to keep tract of the visited path . Every vertex in the graph is visited at most once . Hence the queue size is maximum V . Hence the space complexity if a function of the number of vertices in the graph i.e O(|V|). As regards to the time complexity we run a loop to go over all the vertices in the graph . This is O(|V|) . Also for every vertex found we need to check alls its neighbours and hence the number of edges it is connected to . THis gives us O(|E|) . Thus the complexity can be explained by the notation O(|V| + |E| ) .

rockstar
  • 3,512
  • 6
  • 40
  • 63
3

At the root, you expand out b nodes as the next elements in the search tree. These, if none are the solution, in turn expand out b nodes from each. This continues until a solution is found, which will be at depth d.

Hence: O(b^d)

(I'm not sure where you got the +1 from, however...)

Paul
  • 2,218
  • 1
  • 15
  • 18
  • is this complexity for both space and time? – ms.twenty four Nov 23 '10 at 21:38
  • Yes. Each node needs to be both searched (time), and stored (space), until a solution is found. – Paul Nov 23 '10 at 21:41
  • @ms.twenty four: The algorithm mandates a queue, however if this queue was implemented in an odd fashion (O(scary) insertion and removal) it could affect the overall time complexity. Generally though, if you change this structure too much it will no long be BFS (i.e. - use a stack and it's DFS). – Paul Nov 23 '10 at 21:52
2

If the algorithm were to apply the goal test to nodes when selected for expansion, rather than when generated, the whole layer of nodes at depth d would be expanded before the goal was detected and the time complexity would be O(b^(d+1)).

Mahmoud Mohsen
  • 21
  • 1