4. Consider the Algorithm ARRAYFIND, given below, which searches an array A for
ID: 3754207 • Letter: 4
Question
4. Consider the Algorithm ARRAYFIND, given below, which searches an array A for an element x Input: An element x and an n-element array, AO,.., n-1]. (Indices start from 0) Output: The index i such that xA[i] or -1 if no element of A is equal to x ARRAYFIND(A, x) 2, while i n do 4 5.else 6. 1=1+1 7. return -1 return i Counting assignments, comparisons, and returns only, calculate the worst-case and best-case running times of ARRAYFIND. (Do not use asymptotic notations or parametric constants for this count the exact number of these three simple operations.)Explanation / Answer
i)Worst-case scenario : x is not in A. In this case the following list describes the number of times each line executes :
1.Only 1 time.
2.Since x is not in A, while loop will search through the entire array. Starts with i==0, breaks when i==n. Hence, it runs (n + 1) times.
3.Runs ones for each while loop i.e., i==0 to i==n-1 => n times.
4.Since x is not in A, the previous comparison results false and this line is never executed => 0 times.
5.else is not considered according to the question.
6.Runs ones for each while iteration i.e., i==0 to i==n-1 => n times.
7.Only 1 time, after the while loop finally breaks.
Hence, the exact number of operations performed in the worst-case scenario is 1 + (n + 1) + n + 0 + n + 1 = (3n + 3) times.
ii)Best-case scenario : A[0] == x. In this case the following list describes the number of times each line executes :
1.Only 1 time.
2.Only 1 time, since x will be found in the first iteration.
3.Only 1 time, this line returns true for i=0, since A[0] == x.
4.Only 1 time. Since this line returns the value, subsequent operations are not executed.
Hence, the exact number of operations performed in thebest-case scenario is 1 + 1 + 1 + 1 = 4 times.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.