Binary tree of Routers,expression for minimum no of hops per message?


#1

A group of 2^n−1 routers are interconnected in a centralized binary tree with a router at each tree node . Router 1 communicates with Router j by sending a message to the root of the tree. The root then sends a message back down to j Derive an approximate expression for the minimum number of hops per message for large N , assuming that all the router pairs are equally likely

1). 2N−4

2). N−4/2

3). N−4/2

4). N−4


#2

I recommend seeing this proof:
Give it some time to understand,if you can understand and prove things,you are always one step ahead of everyone.

http://cseweb.ucsd.edu/~pblair/hwsoln/hwsoln.html