Define a recurrence relation. Describe the following problems with the help of examples which can be solved through Divide and Conquer technique and Show its recurrence relation.

(i) Binary Search

(ii) Merge Sort

Solve these recurrence relations with a substitution method

A recurrence relation is a mathematical expression that defines a sequence recursively in terms of one or more initial terms and itself. In other words, it describes the relationship between the terms of a sequence based on the values of preceding terms. Recurrence relations are frequently encountered in various mathematical and computer science problems, providing a way to express a problem in a more compact and elegant form.

Now, let's delve into the problems and their solutions using the Divide and Conquer technique.

### (i) Binary Search

Problem Description:
Binary Search is a classic algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half.

Divide and Conquer Technique:
1. Divide: Divide the array into two halves.
2. Conquer: Recursively search the target in __________ ________ ______ ____ ____ _________ _________ _______ ____ _________ _____.
___ ________ _____ ______ ________ __________.
___ ________ ___ ______ _____ ____ ________ ___ _____ _______ ________.
___ ________ ___ ___ _______ ___ ___.
_________ _____ _____ __________ _________ _________ _____.
________ ______ __________ _____ ________ _________ _____ _______ _____ _______.
_______ ________ __________ _____ _____ _____ _______.
________ _________ ________ ________ __________ ________ ____ _____ ____ _______ __________.
_______ ___ _________ ________ ___ ______ ___ ____ ____ ______ ______ ______.
________ ________ __________ ______ _______ _______ ________ _____ _________ ___ __________.
________ ________ __________ _____ ______ _________ ________ _________ ______ ______ _________.
__________ ________ _________ ___ _____ ____ ____ __________.
___ __________ ________ _______ ___ _____ _________ __________ ___.
_________ ___ ___ _________ _________ __________.
___ ______ ____ ______ ________ ____ _________.
_______ _____ ______ _________ ____ ________ __________ ___ __________ _______ _______ ____.
______ ______ ___ ___ _________ ____ ______ ________ _________.
_______ ___ ___ _________ ______.
_______ __________ ______ ____ ____ ___ ___ ______ ___ __________.
_______ ____ ____ _____ _________ ______ ____ _______ _______ ________.
____ __________ ____ ___ ___ ________ _____ _______ __________ ________.
_________ ____ __________ ___ ____ ________ ________ ______.
__________ _____ ___ _________ ________ ________ __________ ________ ______ _______.
____ ____ ______ _______ ________ _____ ________ __________.
_______ ________ _____ __________ ____.
_____ _________ ________ ____ ________ ______ _____ ____ _________.
_______ ____ _______ ___ __________ _____ ________.
____ ________ ______ ______ ________ _______ ______ _____ ____ ___ _____.
_______ _________ _____ ________ ____ ___ ________ _____ _________ _____ ___.
___ ___ ____ _____ ______ ______ __________ _____ _________ __________ ___.
_______ ______ ________ ______ _________ _________ _____ ___ __________.
_____ ____ _____ ________ ___ ________ ______ _____ __________ ____.
________ ____ ________ ____ ______ ____ ___ _________ _____ __________ ______ _______.
________ ____ _____ ________ _____ _________ ___ ______ ______ ____ ___ _______.
____ ______ ________ ___ _________ _____ _________ __________ _______ _________ _______.
____ ______ __________ ___ __________ _______ ________ ________ ____ __________ __________ ____.
____ ________ _______ ______ ___.
________ _________ _________ ____ _________ ______ _____ _____ ______ _____ _____.
__________ ____ _____ _______ _____ ________.
_____ ______ ___ ______ _________ _________ _________ ________.
_________ _________ _____ ___ ______ ______.
___ _________ ________ __________ ____ ___ ________ ______ ____.
________ ___ ____ __________ ______ _____ _______.
______ _________ ___ _____ ___ _________ _________ ____.
_________ __________ _______ ____ _________ ________ ____ _______ ____.
_____ ____ _______ ______ ____ __________ ________ ________.
_______ ___ __________ ____ ______ ______ ___ ____ __________.
Get Full Answer on WhatsApp