0
$\begingroup$

I read from a book that the jth level (starting from j=0 or the root) of a binary tree with n nodes divides a problem into $2^j$ subproblems, each of size $\frac{n}{2^j}$. I understand where $2^j$ comes from, but where does $\frac{n}{2^j}$ come from?

$n$ includes nodes above the level, right? Hence, how come the sum of the sizes of the subproblems of the subtrees of the level is $n$? Shouldn't it be less than $n$?

  • 0
    Are you sure that it didn’t say $n$ leaves?2012-06-13

1 Answers 1

1

The idea is that if one node of a binary tree representing a divide-and-conquer algorithm has associated 'problem size' $n$, then the two nodes beneath it have problem sizes $x$ and $y$ with $x+y=n$; you split the problem of size $n$ into two sub-problems whose sizes add to $n$. In the best-case scenario, these two subproblems are the same size, which means that each of them is (roughly) $n/2$. By iterating this down you can see that each of the problems two levels beneath are of size roughly $n/4$, the problems on the level below that are of size roughly $n/8$, etc; since you have $2^j$ nodes at level $j$ but the overall size of the problem (the sum of the sub-problem sizes in those nodes) is still $n$, each of those sub-problems must be of size $n/2^j$ so that their sum can be $2^j\cdot(n/2^j)=n$.

  • 0
    Thanks! That makes sense - so each level has the same sum of the sizes of sub-problems. Leaves may numerically represent this, but thinking in terms of size is more intuitive because a recursive algorithm may not traverse all the way to the leaves.2012-06-13