Divide and conquer You are given a sequence A1 n of number s

Divide and conquer You are given a sequence A[1. n] of number, such as A = [8, 1, 3, 4, 7]. A sublist of the numbers, A[i, j] is said to be a sandwich sublist, if all of the values of A[i.j.] are larger than A[i] and smaller than A[j]. For instance, the sublist A[2.5] = [1, 3, 4, 7] in the example above is a sandwich sublist because 3 and 4 are both greater than 1 but less than 7. For this problem you will design a divided and conquer algorithm for computing the longest sandwich interval of a given sequence A [1..n]. You are given a sequence A[i..n| of numbers that are monotonically decreasing, meaning that for each i, A[i] > A[i+11]. You need to find the index of the first negative number. Describe a divide and conquer algorithm for solving this problem that is faster than linear-time. Tasks for the divide and conquer problems: Choose either problem C or problem D, and then complete the following tasks: Write detailed pseudo-code for solving the problem. Write a recurrence T(n) that describes the running time of your algorithm. Solve T(n) to obtain a closed-form solution. Solve T(n) to obtain a closed- form solution. Give the asymptotic complexity class for your algorithm.

Solution

Problem D : First negative

To find the first negative number in a sorted array we have to follow the binary search technique

This code is going to return 2nd half of the array. Finding out the middle value if it is less than zero it is going to return first half of the array otherwise second half.

Consider the above recurrence relation T(n)=T(n/2)+1

T(n/2)=T(n/4)+1

T(n/4)=T(n/8)+1

.....................

T(4)=T(2)+1;

T(2)=T(1)+1

Now sum up left and right sides of equations

T(n)+T(n/2)+T(n/4)+T(n/8)+...+T(2)=T(n/2)+T(n/4)+T(n/8)+.....+T(2)+T(1)+(1+...+1)

Now cross the equal terms on the opposite sides and simplify the remaining sum on the right side.

T(n)=T(1)+log n

T(n)=1+log n

Therefore T(n)=O(log n)

Average case is also Theta(log n).

Best case is Theta(1). Because it can be found on the first hit.

For one particular search the running time is somewhere between best and worst, thus O(log n).