HeapSort as a combine subroutine of MergeSort

This article is taken from my ResearchGate profile. Link . This article is under Creative Commons Licence By (cc-by).

Divide and Conquer Algorithm for Linear Search

Divide and Conquer Algorithm for Linear Search

We have seen the Binary Search Algorithm which searches for an element in a sorted array in logarithmic time. Time complexity associated with it is . 

Recurrence relation of Binary Search: 

Using the same principle of Divide, Conquer, and Combine, we can also utilize this algorithm to find an element in an unsorted array, though the time complexity will be linear .

Recurrence relation of Linear Search: 

#include<iostream>

#include<vector>

using namespace std;

int linear_search(vector<int>&v,int s,int e,int x)

{

    if(s>e)return -1;

    int m=s+(e-s)/2;

    if(v[m]==x)return m;

    int left=linear_search(v,s,m-1,x);

    int right=linear_search(v,m+1,e,x);

    if(left==-1 && right==-1)return -1;

    if(left!=-1)return left;

    else if(right!=-1)return right;

}

int main()

{

    vector<int>v={4,2,6,8,1,2,9,4};

    cout<<linear_search(v,0,v.size()-1,8);

    return 0;

}

Output: 3

Analysis of time complexity:

Sum of an array using Divide and Conquer algorithm

Sum of an array using Divide and Conquer algorithm (DAC)

Finding sum of an array is a very easy task, just add all the elements in a single pass! Time and space complexity associated with this approach is linear and constant respectively. 

In this post, I will show how we can find the sum of an array using Divide and Conquer algorithm.

First of all I would like you to have a glance at What a Divide and Conquer algorithm is? 

Divide and Conquer is an algorithmic strategy used to find solution of a particular problem by recursively breaking down the problem into sub-problems of same type, and when the base condition of the recursion is hit, assemble the results of those sub-problems to form the solution of the original problem.

This strategy often brings considerable optimizations in some while solving some problems. Some popular algorithms that implements Divide and Conquer are:

1. Quicksort

2. Mergesort

3. Binary Exponentiation

4. Quickselect

5. Straseen's algorithm (Matrix Multiplication)

6. Binary Search

The Divide and Conquer strategy can be divided into three parts:

1. Divide: Divide the larger problem into smaller sub-problems of same type.

2. Conquer: Solve the sub-problems by recursively calling until solved.

3. Combine:  Combine the sub-problems to get the final solution of the whole problem.

It becomes very easy to find the time complexity of DAC algorithms using Master Theorem.

Image given below shows how to solve recurrence relations using Master Method.

Now, coming back to the question. We have to find the sum of an array using    DAC. 

Let's formulate the solution:

Sum of an array can be found using breaking the array into two halves, add them and return the sum. Recursively break down the problem into two halves, we the array size becomes 1, return the value of that single element. So simple! 

int sum(int arr[],int start,int end)

{

    if(start==end)

    return arr[start];

    int mid=start+(end-start)/2;

    int left=sum(arr,start,mid);

    int right=sum(arr,mid+1,end);

    return left+right;

}

    int arr[]={1,2,3,-1,4,5,6,7};

    cout<<sum(arr,0,sizeof(arr)/sizeof(int)-1);

output: 27

I have traced the algorithm:

Now, let's find the time complexity of this algorithm. 

Hence, the time complexity is .