Recurrence Tree Method
In this method, we draw a recurrence tree and calculate the time taken by every level of the tree. Finally, we sum the work done at all levels. To draw the recurrence tree, we start from the given recurrence and keep drawing till we find a pattern among levels. The pattern is typically arithmetic or geometric series.
For example, consider the recurrence relation
T(n) = T(n/4) + T(n/2) + cn2
cn2
/ \
T(n/4) T(n/2)If we further break down the expression T(n/4) and T(n/2),
we get the following recursion tree.cn2
/ \
c(n2)/16 c(n2)/4
/ \ / \
T(n/16) T(n/8) T(n/8) T(n/4)Breaking down further gives us following
cn2
/ \
c(n2)/16 c(n2)/4
/ \ / \
c(n2)/256 c(n2)/64 c(n2)/64 c(n2)/16
/ \ / \ / \ / \To know the value of T(n), we need to calculate the sum of tree
nodes level by level. If we sum the above tree level by level,we get the following series T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ….
The above series is a geometrical progression with a ratio of 5/16.To get an upper bound, we can sum the infinite series. We get the sum as (n2)/(1 – 5/16) which is O(n2)
Recurrence Relations Notes for GATE Exam [2024]Advanced master theorem for divide and conquer recurrences:
Recurrence relations are the mathematical backbone of algorithmic analysis, providing a systematic way to express the time complexity of recursive algorithms. As GATE Exam 2024 approaches, a profound understanding of recurrence relations becomes imperative for tackling questions that demand a deep comprehension of algorithmic efficiency. These notes aim to present a concise and illuminating guide to recurrence relations, covering key concepts and techniques that are likely to be assessed in the GATE examination.
Table of Content
- What is Recurrence Relations?
- What is Linear Recurrence Relation?
- How to Solve Recurrence Relations?
- 1. Substitution Method:
- 2. Recurrence Tree Method:
- 3. Master Method:
- Different types of recurrence relations and their solutions:
- Previously Asked GATE Questions on Recurrence Relations: