1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...