I'm trying to do a run-time analysis of an algorithm. The idea is a tree structure is created where any node can have two children. At each iteration of the algorithm there's a 50% chance that a node will create a terminal child, ie that node cannot produce another node.
It runs until either the maximum depth is reached, which is determined randomly also, or until no more nodes can be added because they've all become terminal. For the expected value of the depth I'm using $\frac{n + 1}{2}$ where n is just an integer between 1 and a specified maximum depth.
Then at each level there's a 50% chance it will create a node that can create a node so $2 – 2(\frac{1}{2})^\frac{n + 1}{2}$ will be the expected depth that any particular node will reach, I think. Does this make sense?
Then what will be the expected number of nodes created? I'm not sure how to continue from here.