1. Consider the Algorithm ARRAYFIND, given below, which searches an array A for an element x....
Fantastic news! We've Found the answer you've been seeking!
Question:
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.)
Expert Answer:
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
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...
-
MULTIPLE CHOICE: 6. The stage of production at which the individual jointproducts are identified is referred to as the: A. Split-off point B. Joint point C. Separate identification point D. Relative...
-
Find the stable distribution for the given regular stochastic matrix? 1. 2. 3. 4. 4 L.6 0
-
What is the stated or coupon rate of a bond?
-
An electron and a proton are fired in opposite directions, and at the instant they are nearest each other, their separation distance is \(3.0 \mu \mathrm{m}\) (Figure P28.84). At that instant, the...
-
Three different companies each purchased a machine on January 1, 2008, for $42,000. Each machine was expected to last five years or 200,000 hours. Salvage value was estimated to be $2,000. All three...
-
Operating systems and application programs play vital role in our daily usage of computers. Differentiate between an operating system and an application program give examples each.
-
The manager of the customer service department of a software company is concerned about the number of errors committed in the software development process. A random sample of 250 coding was inspected...
-
3. What should unions do to make themselves more attractive to newly hired Generation Y employees?
-
Craft a personal reflection about your writing process. Specifically, address the following question: 1. How does your self-concept influence your writing? Be specific and thorough 2. What challenges...
-
Imagine you are working for a local non-profit community agency that will be promoting cultural humility education for community members with varying and at times opposing religious affiliations....
-
1. You are sitting in a sled, at rest on a pond covered with nice, thick, frictionless ice. Your own mass is 8 6 . 1 8 6 . 1 kg , , and the mass of the sled when empty is 1 2 . 6 1 2 . 6 kg . . From...
-
As an employer, it's important to identify office safety hazards and making a safe workplace. Sometimes, injuries happen at workplace. Occationaly, the injury is caused by the employer and the...
-
After performing a Grignard synthesis: Question: The dyed fabric will likely smell like mothballs. This is due to a small amount of N, N-dimethyl aniline that is a side-product of the reaction. How...
-
Identify the Critical Infrastructure Physical Protection System Plan.
-
Using Figure 6.2 as a model, illustrate the operation of MAX-HEAPIFY (A, 3) on the array A = ?27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4 8, 9, 0?. Figure 6.2 16 16 3 2 3 10 14 10 4 5 6. 5 6. 14 9. 3. 9 10...
-
Show that if an algorithm makes at most a constant number of calls to polynomial time subroutines and performs an additional amount of work that also takes polynomial time, then it runs in polynomial...
-
What is the running time of QUICKSORT when all elements of array A have the same value?
-
Identify the sample.
-
Test the overall significance of a regression model and identify the components of this test from your computer output.
-
Based on the strategy, what type of sampling technique will be used to identify the sample? a. Why did you choose this type of technique?
Study smarter with the SolutionInn App