GATE SMASHERS Lecture Notes

Topic: Solving Recurrence Relation Using the Substitution Method

Overview

• In previous video, discussed basics of recurrence relations.
• Focused on the recurrence relation of Binary Search:
  T(N) = T(N/2) + C (for N > 1)
  T(1) = 1 (base case)

Recurrence Relation Breakdown

• Equation (1): T(N) = T(N/2) + C
• Check Division:
  • Start with N, then N/2, N/4, N/8, etc.
  • Replacing N with N/2 leads to T(N/4) + C.

Back Substitution Method

1. Substitute T(N/2) into T(N):
   • T(N) = T(N/4) + C + C
   • Write as: T(N) = T(N/4) + 2C
2. Continuing the substitution:
   • Substitute T(N/4) into T(N):
   • T(N) = T(N/8) + C + 2C
   • Leads to: T(N) = T(N/(2^3)) + 3C
3. Generalizing the pattern:
   • After K substitutions, the equation takes the form:
   • T(N) = T(N/(2^K)) + KC

Termination of Function

• To terminate, substitute N with 2^K:
  T(1) = 1 (base case)
• Following substitutions yield:
  • T(N) = T(1) + KC = 1 + KC

Expressing in Terms of N

• To express complexity in terms of N, find K:
  • K = log(N) (because N = 2^K implies K = log(N))
• Substitute back into the equation:
  • T(N) = 1 + C * log(N)*

Final Complexity

• Time complexity is expressed as:
  • Order of log N (Base 2)

Conclusion

• The time complexity of the Binary Search recurrence relation is Order of log N.
• This concludes the method of solving a recurrence relation using the Back Substitution Method.

Key Points

• Recurrence Relation for Binary Search: T(N) = T(N/2) + C
• Back Substitution method is a systematic way to solve recurrence relations.
• The final time complexity derived from the relation is significant for algorithm analysis.

Thank you!