I have a unresolved math problem about non-weighted trees. Suppose we have a tree with branching factor $b$ and depth of most superficial solution as $d$.
From math i know that, if i use a Breadth first algorithm, in every iteration the number of generated nodes is $O(b^{d})$. This is clear to me.
But then i read that if i want an $O$ about the sum of all generated nodes, this is simply $O(b^{d+1})$.But i dont understand why and i wasnt able to prove this result. Can you help me ?
I assume that in your setting visiting a node generates its children (and pushes them onto the BFS queue).
If your solution is at level $d$, then you will never visit a node at level $d+1$, but may potentially generate them all (as children of visited $d$-level nodes) except for the solution-node (which is a solution, so you don't generate children for it). So, if each of $b^{d}$ visited $d$-level nodes generates $b$ children, then you will have $b \cdot b^{d} = b^{d+1}$ of $(d+1)$-level nodes in total.
Furthermore, if $b \geq 2$, we have $$b^0 + b^1 + \ldots + b^d \leq b^{d+1},$$ which gives us the bound for the sum of all nodes: $$b^0 + b^1 + \ldots + b^d + b^{d+1} \leq 2b^{d+1}$$
I hope this helps $\ddot\smile$