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! $n$ refers to the number of leaves I see. A problem is hence seen as a leaf not a node.'2012-06-13
  • 0
    It can, but associating an additive 'size' with each node is really the better way to think about it, because often in the places these sorts of algorithms are used, you won't go all the way down to the size-1 'leaves'. For instance, if you're building a mergesort, then the size of a node represents the size of the subarray (of the original problem) it's responsible for sorting, and the sizes of its children represent the sizes of the two subarrays formed by splitting it in two; but typically you'll only split down to about a size of 5 and then do something like insertion-sort at the leaves.2012-06-13
  • 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