1. Consider the Algorithm ARRAYFIND, given below, which searches an array A for an element x....

 

Transcribed Image Text:

1. Consider the Algorithm ARRAYFIND, given below, which searches an array A for an element x. Input: An element x and an n-element array, A[0,..,n - 1]. (Indices start from 0.) Output: The index i such that x =A[i] or -1 if no element of A is equal to x. ARRAYFIND(A,x) 1. i=0 2. r = -1 while in do if x == A[i] 3. 4. 5. r = i 6. break 7. else 8. 9. i = i + 1 return r A) [10 marks] Counting assignments, comparisons, additions, breaks, and returns only, calculate the exact worst-case and best-case running times of ARRAYFIND. Note that of these 5 operations are all simple and take exactly one time step. Do not count memory-access or other simple operations. As your answer, you need to write down two functions in terms of n; one for the best-case and one for the worst-case. Do not use asymptotic notations or parametric constants for this part. B) [5 marks] Use the Big-O definition to prove that the worst-case running time of ARRAYFIND (calculated in part A) is O(n). C) [5 marks] Use the Big-2 definition to prove that the best-case running time of ARRAYFIND (calculated in part A) is 2(1). D) [5 marks] Explain briefly why we CANNOT say that the running time of ARRAYFIND is (n). (Here the running time is not necessarily for the best-case or for the worst-case input.) 1. Consider the Algorithm ARRAYFIND, given below, which searches an array A for an element x. Input: An element x and an n-element array, A[0,..,n - 1]. (Indices start from 0.) Output: The index i such that x =A[i] or -1 if no element of A is equal to x. ARRAYFIND(A,x) 1. i=0 2. r = -1 while in do if x == A[i] 3. 4. 5. r = i 6. break 7. else 8. 9. i = i + 1 return r A) [10 marks] Counting assignments, comparisons, additions, breaks, and returns only, calculate the exact worst-case and best-case running times of ARRAYFIND. Note that of these 5 operations are all simple and take exactly one time step. Do not count memory-access or other simple operations. As your answer, you need to write down two functions in terms of n; one for the best-case and one for the worst-case. Do not use asymptotic notations or parametric constants for this part. B) [5 marks] Use the Big-O definition to prove that the worst-case running time of ARRAYFIND (calculated in part A) is O(n). C) [5 marks] Use the Big-2 definition to prove that the best-case running time of ARRAYFIND (calculated in part A) is 2(1). D) [5 marks] Explain briefly why we CANNOT say that the running time of ARRAYFIND is (n). (Here the running time is not necessarily for the best-case or for the worst-case input.)

Answer rating: 100% (QA)

A WorstCase Running Time In the worstcase scenario the element x is not present in the array or is t... View the full answer