Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By MacstersUndead
  • 1 Post By MacstersUndead

Thread: How can calculate formula for nodes in Fat-Tree?

  1. #1
    Junior Member
    Joined
    Nov 2016
    From
    Malaysia
    Posts
    49

    How can calculate formula for nodes in Fat-Tree?

    Hello,
    We have a fat-tree and diameter is = 2h (h is height of tree)
    How can proof how many nodes exists in tree?
    Thanks
    Attached Thumbnails Attached Thumbnails How can calculate formula for nodes in Fat-Tree?-fast.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2009
    Posts
    349
    Thanks
    48

    Re: How can calculate formula for nodes in Fat-Tree?

    I would use induction to prove that given n nodes at h=0 (the top level), that P: "the number of nodes S = n + \sum\limits_{h=1}^h 2n"

    The base case would be to prove that the statement is true for P(h=1).
    The inductive step would be to suppose S = n + \sum\limits_{h=1}^h 2n for P(h).
    Then you would use the inductive step to show S = n + \sum\limits_{h=1}^{h+1} 2n for P(h+1).

    Let me know if you have further questions.
    Last edited by MacstersUndead; Jan 8th 2017 at 08:00 PM.
    Thanks from life24
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    349
    Thanks
    48

    Re: How can calculate formula for nodes in Fat-Tree?

    I made a mistake.
    P: "The number of nodes in the graph is \sum\limits_{h=0}^h 2^h*n (ie. for each new level, the number of nodes to be added is doubled based on the number of the previous level.)

    The rest of the process would be the same.
    ie. Prove the base case. Suppose for P(h). Show it's then true for P(h+1)
    Thanks from life24
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2016
    From
    Malaysia
    Posts
    49

    Re: How can calculate formula for nodes in Fat-Tree?

    Quote Originally Posted by MacstersUndead View Post
    I made a mistake.
    P: "The number of nodes in the graph is \sum\limits_{h=0}^h 2^h*n (ie. for each new level, the number of nodes to be added is doubled based on the number of the previous level.)

    The rest of the process would be the same.
    ie. Prove the base case. Suppose for P(h). Show it's then true for P(h+1)
    Thank you,
    But I did not understand. I think we used Geometric progression for calculate this.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    349
    Thanks
    48

    Re: How can calculate formula for nodes in Fat-Tree?

    My equation was equivalent the form of a geometric progression
    https://en.wikipedia.org/wiki/Geomet...ometric_series

    See this section for the closed form of geometric series. In this case, "a" would be the number of base nodes at h=0 and "n" would be the height.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting nodes in a tree (series?)
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Nov 28th 2012, 02:57 PM
  2. Need a formula to calculate the speed variation.
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: Jun 1st 2011, 05:25 AM
  3. Matrix Tree Formula
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Feb 14th 2011, 06:54 AM
  4. Number of nodes in a tree
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Feb 10th 2009, 06:02 AM
  5. Formula to calculate indexes from row and column
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 18th 2008, 05:53 AM

/mathhelpforum @mathhelpforum