Consider the following description of a recursive algorithm in design and analysis of algorithm.

Question:

Design and Analysis of Algorithms.

Consider the following description of a recursive algorithm:
“The algorithm splits the input into three equal parts in constant time, process each part recursively and finally combines the solution in linear time”.
Formulate a recurrence and solve it to compute the total execution time of the algorithm.
(Note: You can use any method for solving the recurrence.))

Summary:

Basically, in the design and analysis of algorithms, a divide and conquer algorithm can be designed for a given concept of a recursive algorithm. The divide and conquer method is used in merge sort.

Explanation:

Divide and conquer method:

It is the best-known design technique. It works  accordingly:

Divide the problem into smaller parts.

Independently solve the parts.

Combine these solutions to get the overall solution.

 

Merge sort:

It is a perfect example of divide and conquer. It sorts a given array A[0…n-1] by dividing it into two halves A[0…..((n/2)-1)] and A[n/2……n-1], sorting each of them recursively and then merging the two smaller sorted arrays into a single sorted one.

 

Algorithm for merge sort using divide and conquer method:

Algorithm Merge Sort (A[0....n-1])

A by recursive merge sort

//input: An array A[0...... n-1] of orderable elements//output:

Array A[0...n-1] sorted in increasing order

ifn>1

copy A[0.....((n/2)-1)] to B[0.....((n/2)-1)]

copy A[n/2......n-1] to C[0.....((n/2)-1)]

Merge Sort (B[0.....((n/2)-1)] )

Merge Sort(C[0.....((n/2)-1)] )

Merge(B,C,A).

Source code:

#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    i = 0; 
    j = 0; 
    k = l; 
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
 
void printArray(int A[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}
int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
  
    printf("Given array is \n");
    printArray(arr, arr_size);
  
    mergeSort(arr, 0, arr_size - 1);
  
    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

Output:

Time complexity:

Thus, a recursive solution is found for the merge sort algorithm which follows the divide and conquers approach. There are three stages, divide, conquer and combine. For dividing, it takes only constant time and for combining it takes linear time.

The recurrence of the entire algorithm is :

T(n) = 3 T(n/3 ) + O(n).

On solving it we get the time complexity of the merge sort algorithm using the divide and conquer method.

T(n) = O(n log₃n).

 

Also, read Dijkstra’s algorithm to find the shortest path.