Exploring the Cost of a Recursion Tree

[evinda]

Hi! (Wave)

According to my notes:

$$T(n)=T\left(\frac{n}{2} \right)+T\left(\frac{n}{4} \right)+T\left(\frac{n}{8} \right)+n$$

Th recursion tree is this:

https://www.physicsforums.com/attachments/3626

Cost per level $i \to \left( \frac{7}{8} \right)^{i-1}n, i \geq 1$

Leaf per level $i \to 3^i, i \geq 0$

$$\text{Total Cost=} 3^D O(1)+ \sum_{i=1}^D \left ( \frac{7}{8}\right)^{i-1} n$$

$$\frac{n}{2^D}=1 \Rightarrow D=\log_2 n$$

Could you explain me why we have to add $3^D$ at the sum of costs of the levels, in order to find the total cost? Also, why do we find $D$, from $\frac{n}{2^i}=1$ and not for example from $\frac{n}{4^i}=1$ or from $\frac{n}{8^i}=1$ ? (Worried)

 

[Valkarie]

The $3^D$ is added to the total cost because there are three leaf nodes for every level, so for every level that you go down in the recursion tree, you have three more leaf nodes to account for. The reason why we use $\frac{n}{2^i}=1$ and not something else is because that's the base case of the recursion, i.e. when we reach the leaves of the tree. This is the point where we stop recursing and start adding up the costs. We use $2^i$ because that's the number of leaf nodes we have at each level, i.e. $\frac{n}{2^i}=1$ tells us that we have reached a level with one leaf node.