Time complexity of Breadth First Search, why and how?

In summary, the time complexity for BFS on a tree with a goal node n is , where b is the branching factor and d is the depth of the tree. In the given example, b is 2 and d is 4, resulting in a time complexity of .
  • #1
shivajikobardan
674
54
Firstly, how is time complexity of BFS .
Say I have this tree with goal n, how do I calculate time complexity for it? Assume left to right traversal. I know the answer is a,b,c,x1,d,e,f,i,j,k,g,h,z,l,m,n. But I am not sure how to calculate time complexity here using the above formula
1643514071533.jpeg
 
Technology news on Phys.org
  • #2
. The time complexity for BFS on this tree is where b is the branching factor and d is the depth of the tree. In this case, b is 2 (for each node there are two child nodes) and d is 4 (the depth of the tree is 4 levels). Therefore the time complexity for BFS on this tree is .
 

Similar threads

Replies
1
Views
2K
Replies
6
Views
2K
Replies
31
Views
5K
Replies
36
Views
6K
Replies
36
Views
6K
Replies
4
Views
2K
Replies
9
Views
2K
Back
Top