# Time complexity for Breadth-First search

I would like to know why the average number of nodes at level d in BFS in a search tree is $\frac{1+b^d}{2}$ as given in this lecture(p.15)?(Here b is the branching factor of the tree and d is the depth of the tree)

I think that as average tells us to take the sum of the numbers and divide by how many numbers are present here we should consider the sum of nodes at level d(considering the deepest level in search tree) and the number of nodes at level d.

Sum of nodes at level d : $b+\dots+b$(d+1 times since we consider the initial depth as zero)=$b(d+1)$

Number of nodes at level d : $b^d$

So the average number of nodes at level d would be $\frac{b(d+1)}{b^d}$

• What do you mean by sum of nodes at level $d$? – Agent Gotse May 27 '16 at 9:20
• Please include all the required information in your post. 1) Which algorithm are we talking about? 2) Which class of graphs and which random distribution over them do we assume? – Raphael May 27 '16 at 11:36

I think "average" in this context means how many nodes would the search algorithm examine on average before the element you are looking for is found. Best case scenario, you would find it immidiately at depth $d$ hence you would examine 1 node. Worst case scenario, the element is the last you examine on that level or not there at all, hence you would examine all nodes at level $d$, so you would examine $b^d$ nodes. Thus, on average you would need to examine $\frac{b^d+1}{2}$ nodes on that level.
• :That's right.So whether the average number of nodes in DFS is $\frac{1+d}{2}$? – justin May 27 '16 at 10:27