Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
Are you sure that it didn’t say $n$ leaves? –  Brian M. Scott Jun 13 '12 at 4:54

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Thanks! $n$ refers to the number of leaves I see. A problem is hence seen as a leaf not a node.' –  David Faux Jun 13 '12 at 14:08
    
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. –  Steven Stadnicki Jun 13 '12 at 15:30
    
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. –  David Faux Jun 13 '12 at 15:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.