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) $.
