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}$
Time complexity for Breadth-First search
graphs;algorithm analysis;runtime analysis;graph traversal