Recurrence Relation and Binary Search Algorithm

Introduction

• Definition: Recurrence Relation - A function calling itself repeatedly.
• Purpose: Used in competitive exams, college/university exams, and placements.

Binary Search Algorithm

• Usage: Search an element in a sorted array.
• Conditions: Array must be sorted beforehand.

Example

• Array: 10, 20, 30, 40, 50, 60, 70
• Initial Pointers:
  • I (First index): 1
  • J (Last index): 7
• Search Element: Example X = 30
• Mid Calculation: Mid = (I + J) / 2
  • Example: (1 + 7) / 2 = 4
  • Array mid-element position: 4
• Comparison Steps:
  • Mid Element (A[mid]) vs X
  • If A[mid] == X, search is complete.
  • If A[mid] > X, continue search in left sub-array.
  • If A[mid] < X, continue search in right sub-array.

Recurrence Relation Concept

• Problem Division: Original problem N is divided into two subproblems: N/2
• Selection: Choose the subproblem containing the search element.
  • Recurse on the selected subproblem.
  • Subproblems keep halving: N/2, N/4, N/8, etc.

Recurrence Relation for Binary Search

• Relation: T(N) = T(N/2) + O(1)
  • Explanation: Time taken T(N) is equal to time for one subproblem T(N/2) plus constant time for comparison and mid calculation.

Methods to Solve Recurrence Relations

1. Substitution Method (Back Substitution)
2. Master Theorem
3. Recursion Tree Method

Next Steps

• Upcoming videos will delve into solving recurrence relations using the substitution method.

Conclusion

• Recurrence relations help to understand the performance of recursive algorithms like Binary Search.