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
-
Explore the Department of Employment of Social Development Canada (EDCS) website. Choose any one position (any location, any job type) and search for information that can be used for the purpose of...
-
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
-
On June 1, 2014, Natalie becomes both a shareholder and chief administrator of operations of Koebel's Family Bakery Ltd. Aft er much discussion with her parents, Janet and Brian, Natalie decides not...
-
Capital budgeting has three phases: (1) identification of potential investments, (2) selection of investments, and (3) postaudit of investments. What is the accountants role in each phase?
-
Marathon Running Shoes reports the following: 2016 Feb. 4 Recorded credit card sales of $96,000, net of processor fee of 1 %. Ignore Cost of Goods Sold. Sep. 1 Loaned $23,000 to Jess Prichett, an...
-
1. Philla Singer received the following receipts and accruals for the 2020 year of assessment. A - Rental income from commercial property R200 000 B Revenue from sales of residential property held...
-
Montreal Electronics Company manufactures two large-screen television models: the Nova, which has been produced for 10 years and sells for $900, and the Royal, a new model introduced in early 20x0,...
-
P12-3C The partners in Salmon Company decide to liquidate the firm when the balance sheet shows the following. SALMON COMPANY Balance Sheet April 30, 2017 Assets Liabilities and Owners' Equity Cash...
-
8)Differentiate Va+a+a+x w.r.t x.
-
What is the payout ratio for a firm with EPS (earnings per share) of $2.50 and dividend per share of $2.00?
-
Rory Company has an old machine with a book value of $123,000 and a remaining five- year useful life. Rory is considering purchasing a new machine at a price of $142,500. Rory can sell its old...
-
(x+x-a 9) Differentiate y = log - w.r.t x.
-
PROBLEMS IN HANDLING COMPLAINTS Pioneer Electronics Store, one of the leading electronic stores in Hyderabad ells batteries, all shapes and sizes, all voltages and prices. One particular battery...
-
Here are some data for five companies in the same industry:Company CodeABCDEEBIT12.9636.96120.96?4.56112.56Interest expense5.4015.4050.402.401.40Calculate a measure o 2 answers
-
A 2500-lbm car moving at 15 mi/h is accelerated at a constant rate of 15 ft/s 2 up to a speed of 50 mi/h. Calculate force and total time required?
-
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?
-
The effective working of the financial aspects of a market economy rests on the validity of the underlying premises of integrity in the conduct of business and reliability in the provision of...
-
Discuss the main arguments for dispensing with all SSAPs and FRSs.
-
To what extent do you think FRSs should take economic consequences into account?
Study smarter with the SolutionInn App