Comparsion done at Level i on a tree

1. Dec 13, 2008

Gear2d

In class we had done and average case of a decision tree, and I am confused as to have at Level i you would have 2i + 1 comparison. How do we arrive at this?

I see at level 0 you have 1 node so 2(0) + 1 = 1 comparison

Level 1 with 1 node you have 2(1) +1 = 3 comparisons

Level 2 with 4 nodes you have 2(2) + 1 = 5 comparisons

Level 3 with 8 nodes (2^3) you have 2(3) + 1 = 7 comparisons

Level 4 with 16 nodes you have 2(4) + 1 = 9 comparisons

I am not seeing the connection between the number of nodes and number of comparisons.

Last edited: Dec 13, 2008