Engineering, 06.05.2020 07:31, mikeeway33

Suppose you have an array of n items (the "member items") and a separate list of k items (the "test items"). The member items are not stored in any particular order. You want to know which of the k test items belong to the set of member items. Here are two different ways to solve the problem: .

Algorithm 1: Look up each test item in the array of member items, using sequential search. .
Algorithm 2: Sort the array of member items, using an optimal comparison- based sorting algorithm, and then look up each test item in the array of member items using binary search Answer the following questions, and briefly justify your answer to each part.

(a) What is the worst-case running time of Algorithm 1 (asymptotically, in terms
(b) What is the worst-case running time of Algorithm 2 (asymptotically, in terms
(c) For a given value of n, for what values of k is Algorithm 2 at least as efficient as of n and k)? of n and k)? Algorithm 1?

Answers: 3

Show answers

Other questions on the subject: Engineering

Engineering, 04.07.2019 18:10, yasminothman02

An air conditioning system consist of a 5 cm diameter pipe, operating at a pressure of 200 kpa. the air initially enters the pipe at 15°c with a velocity of 20 m/s and relative humidity of 80%. if the heat supply throughout the process is 960 w, determine the relative humidity and the temperature at the outlet

Answers: 3

continue

Engineering, 04.07.2019 18:10, niyawilliams23

Asingle-geared blanking press has a stroke of 200 mm and a rated capacity of 320 kn. a cam driven ram is assumed to be capable of delivering the full press load at constant force during the last 15 percent of a constant-velocity stroke. the camshaft has an average speed of 90 rev/min and is geared to the flywheel shaft at a 6: 1 ratio. the total work done is to include an allowance of 16 percent for friction a) estimate the maximum energy fluctuation b) find the rim weight for an effective diameter of 1.2 m and a coefficient of speed fluctuation of 0.10

Answers: 1

continue

Engineering, 04.07.2019 18:10, skpdancer1605

Ariver flows from north to south at 8 km/h. a boat is to cross this river from west to east at a speed of 20 km/h (speed of the boat with respect to the earth/ground). at what angle (in degrees) must the boat be pointed upstream such that it will proceed directly across the river (hint: find the speed of the boat with respect to water/river)? a 288 b. 21.8 c. 326 d. 30.2

Answers: 3

continue

Engineering, 04.07.2019 18:10, katelynn73

Atmospheric air has a temperature (dry bulb) of 80° f and a wet bulb temperature of 60° f when the barometric pressure is 14.696 psia. determine the specific humidity, grains/lb dry air. a. 11.4 c. 55.8 d. 22.5 b. 44.1

Answers: 1

continue

Do you know the correct answer?

Suppose you have an array of n items (the "member items") and a separate list of k items (the "test...