Consider the following algorithm:

algorithm R(arr,v):

// Pre: Array arr is a 1-dimensional length-n array of integers, and v is an integer. // Post:

1 for i 1, 2, ..., n loop 2 if M[i] = v then 3 return i 4 return -1

(a) What does the code fragment compute and what is the corresponding post-assertion Post? (b) Derive the best-case scenario (identifying all inputs (arr, v) that yield the best-case scenario) and the best-case running time of algorithm R(arr, v), and (c) Derive the worst-case scenario (identifying all inputs (arr, v) that yield the worst-case scenario) and the worst-case running time of algorithm R(arr, v).

(All of your answers should be in exact forms (not in asymptotic notations) in terms of R, n, and v.)