Question

Algorithm 1 CS317FinalAlgorithm (A[O..n-1]) ito while i<n - 2 do if A[i]A[i+1] > A[i+2) then return i it i+1 return -1

Using the pseudocode answer these questions

Answer 1

1.)

The given pseudo code traverses the array until  the present element power next element is greater than the next next element if it finds so then it would return the index of the element

For example consider the array 1 2 3 5

current element is 1 next element is 2 and next next element to 1 is 3

so if =1 is not greater than 3 so we traverse the array

1-

now index is at 2 and =8 >5 since this satisfies index 1 would be returned (given 0 indexing)

23

After complete traversal of the array if it could not find out the element then it would -1 .

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

Given array = {1, 2, 3, 4, 5}

iteration i=0

a[i]=1 a[i+1]=2 a[i+2]=3

so =1 is not greater than 3 so increment i

1-

Now i=1

a[i]=2 a[i+1]=3 a[i+2]=4

=8 > 4 since the condition is satisfied i will be returned

23

Here i=1 so index 1 will be returned.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

2.)Worst case input is if we do not find the index that is satisfying the given condition

So if in the given array after traversing the whole array if the index is not returned that means if the condition $A[i]^{A[i+1]}>A[i+2]$ is not satisfied for any of the elements in the array then it is the worst case input

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

3)Best case input is the one if the condition is satisfied in the first location that is returning the index 0 as output is the best case input

For example consider an array 2 3 4 1

$2^{3}=8>4$

here the condition is satisfied in the first location hence it would index of 2 which is 0

this is the best input case