Let n be a nonnegative integer. In this problem, we are given an array of intege
ID: 3663369 • Letter: L
Question
Let n be a nonnegative integer. In this problem, we are given an array of integers A[ 1,..., n] and an integer x. We wish to compute the successor of x in A, which we define as the smallest element in A which is greater than x. For example, if A = [8,4,2, -7, -5,6,2] and x = 2, then the successor of x in A is 4. Similarly, the successor of -6 in A is -5. We define the successor of x in A to be infinity if there is no integer in A which is greater than x. Here is a recursive algorithm which takes as input A[ 1,... ,n] and an integer x, and returns the successor of x in A, as defined above. procedure Successor(A[1,..., n], x) if n = 0 then return infinity s := Successor (A [1,...,n - 1],x) if (A[n] > x and A[n]Explanation / Answer
a)
as per the algorithm we are searching for the succesor of x using recursion technique.if n=0 it returns infinity which is true else it repeatly calls the function again.
The condition for the check is correct.
if (A[n]>x and A[n]<s) then s=A[n] it checks whether the succesor is greater than x and it is less than the already existing greatest succesor of that number if yes then it updates s=A[n]. Now this s or A[n] becomes the nexr successor.
b)
As per the recursion here the recurrence relation will be
T(n) = T(n-1) +O(1)
c)
It will be O(n) because there is no complicated recursion here. Only the value of n is being decreased by 1 in every loop.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.