Recurrence Relations and Trees Notes

Recurrence Relations and Trees

• Concept of Recurrence Relations (RR):

  • A recurrence relation defines a relation among the values of a sequence.
  • Important to know how to calculate specific values of recurrence relations and methods to derive closed forms.

• Trees in Recurrence Relations:

  • Trees provide a structured graphical representation of recurrence relations.
  • Useful for visualizing the evaluation of a recurrence and deriving closed formulas.

• Example of Recurrence Relation:

  • Given RR: $T(n) = 2T(n/3) + 1$
  • Evaluate for smaller values to build a tree:
    • Starting with $T(9)$:
    • The root node is $T(9)$ with contribution from child nodes, leading to a tree representation.
    • Contributions can be summed across levels: e.g., for $T(9)$, sum the contributions with node values.

• Tree Representation:

  • Example tree from $T(n)$:
  • At the root: $T(9)$ contributes 1.
  • For child levels:
    • $T(3)$ contributes subsequently through its nodes leading to levels with aggregate values.

• Identifying Tree Levels:

  • Levels are indexed starting from 0:
  • Level 0 has 1 node contributing value, increasing with each level up to level $k$.
  • Number of nodes at level $(k)$ is given by $2^k$, representing full binary tree like structures.

• Calculating Total Values Level-wise:

  • Create a table to track nodes per level:
    | Level | Nodes | Value per Node | Total Value |
    |-------|-------|----------------|-------------|
    | 0 | 1 | 5 | 5 |
    | 1 | 2 | 3 | 6 |
    | 2 | 4 | 1 | 4 |

• Total Contribution:

  • The final total can be computed by summing contributions from all levels up to level $k$.

• Final Result from the Tree:

  • Depending on tree levels, the total contributions can be calculated and simplified, leading to closed forms for the original recurrence relation.

• Change of Base for Logarithmic Functions:

  • Utilize change of base formulas for logarithmic computations to simplify expressions involving logs in your calculations.

• Significant Results:

  • Using trees and level contributions leads to clearer identification of the closed formula for recursion relations such as:
  • $T(n) = bigO(n log n)$

• Practice and Application:

  • Test on various forms of $T(n)$ RRs using different initial values and summation levels to build proficiency in finding solutions through trees.