Question

Answer the following questions(5pt)
a)   Write an algorithm that finds the largest item in an array of n items by using divide-and-conquer algorithm design pattern.
b)   Analyze the worst-case time complexity of your algorithm in (a), and show the results using asymptotic notation (ϴ)

Answer 1

package search;

// Part (A)

//finds the largest item in an array of n items by using divide-and-conquer

public class DivideAndConqureSearch {

public static int mergeSearch(int ar[],int l,int r){

if(l<r){

int mid=(l+r)/2; //take mid index

int f=mergeSearch(ar,l,mid); //call mergesort on first half and return max in first half subaaray

int s=mergeSearch(ar,mid+1,r); //call mergesort on second half and return max in second half subaaray

int res=marge(ar,l,r,mid); //find the max in both side

return Integer.max(f, Integer.max(res, s)); //now return max of all three

}

return -1;

}

public static int marge(int ar[],int l,int r,int mid){

int res=Integer.MIN_VALUE; //Initialize res with min integer value

for(int i=l;i<=mid;i++){ //find the max in first half

if(ar[i]>res){

res=ar[i];

}

}

int res1=Integer.MIN_VALUE; //Initialize res1 with min integer value

for(int i=mid+1;i<=r;i++){ //find the max in second half

if(ar[i]>res){

res1=ar[i];

}

}

return Integer.max(res, res1); //return max of both

}

//Driver program to test

public static void main(String[] args) {

int ar[]={20, 13, 4, 34, 5, 15, 90, 100, 75, 102};

System.out.print(mergeSearch(ar,0,ar.length-1));

}

}

// Part (B)

/*worst case of merge sort is NlogN

* Merge sort

* {20, 13, 4, 34, 5, 15, 90, 100, 75, 102}

* / \

* {20, 13, 4, 34, 5} {15, 90, 100, 75, 102}

* / \ / \

* {20, 13, 4}{34, 5} {15, 90, 100,} {75, 102}

* / \ / \ / \ / \

*{20, 13} {4} {34} {5} {15, 90} {100} {75} {102}

* / \ / \

*{20} {13} {15} {90}

*

*Height of above tree is Log(N)

*to merge the array two temp array it will take o(N) in worst case

*so Worst Case time complexity it O(Nlog(N))

*

*

*/

output

102