Scribd
Upload
10 views2 pages

Solve Recurrence Relations Iteratively

A recurrence relation defines a function in terms of its values at smaller inputs, commonly arising in recursive algorithm analysis. The direct (iterative) method involves expanding the recurrence until a pattern is identified, allowing for simplification and computation of the time complexity. An example demonstrates this method, concluding that T(n) = Θ(n log n) for the recurrence T(n) = 2T(n/2) + n.

Uploaded by

mipef18567
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views2 pages

Solve Recurrence Relations Iteratively

A recurrence relation defines a function in terms of its values at smaller inputs, commonly arising in recursive algorithm analysis. The direct (iterative) method involves expanding the recurrence until a pattern is identified, allowing for simplification and computation of the time complexity. An example demonstrates this method, concluding that T(n) = Θ(n log n) for the recurrence T(n) = 2T(n/2) + n.

Uploaded by

mipef18567
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Solving Recurrence Relations: Direct (Iterative)

Method

What is a Recurrence Relation?


A recurrence relation is an equation that defines a function T (n) in terms of its value(s)
at smaller input sizes. Recurrences often arise in the analysis of recursive algorithms.
Example:
T (n) = 2T (n/2) + n
This describes the time complexity of Merge Sort.

Direct (Iterative) Method


The direct method, also known as the iteration method, involves expanding the recur-
rence step by step until a pattern emerges. Then we compute a general form and simplify
it.

Steps of the Method


1. Write the recurrence relation.
2. Expand the recurrence by substituting recursively.
3. Continue expanding until the input size becomes the base case.
4. Identify the pattern and sum the terms.
5. Simplify the expression.

Example: Solve T (n) = 2T (n/2) + n


We assume T (1) = Θ(1) and n is a power of 2.

1
CS - Algorithms Introduction to Recurrences

Step-by-Step Expansion:

T (n) = 2T (n/2) + n
= 2[2T (n/4) + n/2] + n
= 4T (n/4) + 2n + n
= 4[2T (n/8) + n/4] + 3n
= 8T (n/8) + 4n + 3n
= ...
= 2k T (n/2k ) + kn

Stop When:
We stop expanding when n/2k = 1 ⇒ 2k = n ⇒ k = log2 n

Substitute Back:
T (n) = 2log2 n T (1) + n log2 n = n · T (1) + n log2 n

Since T (1) = Θ(1), we get:


T (n) = Θ(n log n)

Conclusion
The direct method is a useful tool to solve divide-and-conquer recurrences. By expanding
and identifying patterns, we can often find the time complexity of recursive algorithms.

Tip for Students


Always try this method when the recurrence follows a clear divide pattern (e.g., T (n) =
aT (n/b) + f (n)). It’s especially useful for algorithm analysis like Merge Sort, Binary
Search, etc.

You might also like