Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Comparsion done at Level i on a tree

  1. Dec 13, 2008 #1
    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
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted



Similar Discussions: Comparsion done at Level i on a tree
  1. Smoker Tree Diagram (Replies: 2)

  2. Tree diagram problem (Replies: 3)

Loading...