Computer Engineering(CE)

Question 1: Algorithms

August 2015

### Solution 1

First, it is fairly straightforward to see that the depth of the tree is given by $\log_b n$. Observe that the cost of each leaf is $T(1) = \Theta(1)$. The subproblem size decreases by a factor of $b$ every time we descend a level in the tree, so it must be true that when the subproblem size is 1, the equality $n/b^j = 1$ must hold. Then the depth of the tree, $j$, must be $\log_b n$.

For the second part of the problem, not that the subproblem size of each leaf is $T(1)$, so the question of how many leaves are contained in the tree is equivalent to the question posed. Now let us consider the root of the tree. This node has $a$ children, and each child will have $a$ children of its own. Thus the number of nodes at level $j$ of the tree is given by $a^j$. Thus since the depth of the leaves is $\log_b n$, we have that the number of leaves in the tree is $a^{\log_b n} = n^{\log_b a}$, and that the total contribution of the leaves is bounded by $\Theta(n^{\log_b a})$.

For the final part of the problem, recall that there are $j$ nodes at the $j$-th level of the tree, so we are done if we can find the contribution of each node at the $j$-th level. Now recall that the cost of the root node is given by $f(n)$. The function $f(\cdot)$ is independent of level, so it is easy to see that the cost of a node at the $j$-th level of the tree is given by $f(n/b^j)$ (since the size of a subproblem at level $j$ is given by $n/b^j$). Then it follows from the expressions for number of nodes at the $j$-th level and cost of each node at the $j$-th level that the cost of all the nodes on the $j$-th level is $a^j f(n/b^j)$.