Task 1: Consider the following pseudocode function that describes the R0 Search algorithm: function R0(key,A1,A2,N) for 0 <= i < ceiling(N/2) if(A1[i] == key): return 2*i for 0 <= i < floor(N/2) if(A2[i] == key): return 2*i + 1 return -1 In this pseudocode floor(x) and ceiling(x) are the mathematical functions that, respectively, give the largest integer smaller than or equal to x and give the smallest integer larger than or equal to x. You may assume that calculating the floor(x) and ceiling(x) takes constant time. For this algorithm address the following: Identify, and describe very briefly in words, the best-case inputs and the worst-case inputs. Recall that there are four inputs to R0.
Task 1: Consider the following pseudocode function that describes the R0 Search algorithm:
function R0(key,A1,A2,N)
for 0 <= i < ceiling(N/2)
if(A1[i] == key): return 2*i
for 0 <= i < floor(N/2) if(A2[i] == key):
return 2*i + 1
return -1
In this pseudocode floor(x) and ceiling(x) are the mathematical functions that, respectively, give the largest integer smaller than or equal to x and give the smallest integer larger than or equal to x. You may assume that calculating the floor(x) and ceiling(x) takes constant time. For this algorithm address the following:
-
Identify, and describe very briefly in words, the best-case inputs and the worst-case inputs. Recall that there are four inputs to R0.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
