Algoorithm

Introduction to theory of

Algorithm

Assignment 1

Submitted byRAHUL PAUL

1> Referring back to the searching problem observe that if the sequence A is sorted, we

can check the midpoint of the sequence against v and eliminate half of the sequence from

further consideration. The binary search algorithm repeats this procedure, halving the size

of the remaining portion of the sequence each time. Write pseudocode, either iterative or

recursive for binary search. Argue that the worse case running time of binary search is Θ(lg

n).

SolutionWe can do binary search only on a sorted array. So for binary search a sorted array A, a searching

element n and a range [low … high] of the array is required. The procedure compares the number n to

mid point of the array and then choose which half of the given range should be searched further for

finding the location.

ITERATIVE-BINARY (A,n,low,high)

BINARY(A,n,low,high)

while low ≤ high

mid = (low+high)/2

if n =A[mid]

return mid

if n > A[mid]

low = mid+1

BINARY(A,n,mid+1,high)

else

high = mid-1

BINARY(A,n,low,mid-1)

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

= [T(N/4)+ Θ(1)] + Θ(1)

RECURSIVEwhile low ≤ high

mid = (low+high)/2

if n =A[mid]

return mid

if n > A[mid]

RECURSIVEelse

RECURSIVE-

= [T(N/8)+ Θ(1)] + Θ(1)+ Θ(1)

.

.

.

=[T(n/2i) + i

let 2i = x => lg(2i) = lg x => i* lg 2 = lg n => i = lg n

so, it is , lg n + 1

the Solution is T(n) = Θ(lg n).

2. Observe that the while loop of lines 5-7 of the insertion sort procedure in section 2.1

uses a linear search to scan(backward)through the sorted sub-array A[1…j-1]. Suppose we

can also use a binary search instead of linear search. Answer the following questions:

(1) How many element moving operations (i.e, A[i+1]=A[i]) are required if the binary

search is used? How many element moving operations are required if the linear search is

used? Justify your answer for the worst case.

(2) How many comparisons are required if the binary search is used? How many

comparisons are required if the linear is used? Justify...