Using a recursion tree helps find an asymptotic upper bound for recurrence relations by representing recursive calls as a tree, summing costs at each level, and deriving the upper bound in Big O notation.
Using a recursion tree is a method to find an asymptotic upper bound for recurrence relations, which are equations that define sequences recursively. A recursion tree represents each recursive call of the sequence as a node, with the original call at the root. Each level of the tree corresponds to a recursive call and the cost at each level indicates the amount of work done at that stage of the recursion.
By summing the costs at each level, we can determine the total cost of the algorithm. The height of the tree helps indicate the depth of recursion and therefore the maximum number of recursive calls made. Finally, the asymptotic upper bound is typically expressed using Big O notation, which provides a simplified analysis of an algorithm's efficiency in terms of input size, ignoring constants and less significant terms.
The final answer will be in the form of O(f(n)) where f(n) expresses the dominant factor determining the cost in relation to the size of the input n. For example, if the work done at each level of the recursion tree is found to double as we go deeper, and the height of the tree is h, then the total work done is O(2^h), indicating exponential growth.
So, developing and analyzing a recursion tree allows us to derive a good asymptotic upper bound that characterizes the time complexity of recursive algorithms in terms of Big O notation.