Do either of the following modifications to the Shellsort routine coded in Figure 7.4 affect the worst-case

Question:

Do either of the following modifications to the Shellsort routine coded in Figure 7.4 affect the worst-case running time?

/** * Shellsort, using Shell's (poor) increments. 3 * @param a an array of Comparable items. 4 */ public static <AnyType

a. Before line 11, subtract one from gap if it is even.
b. Before line 11, add one to gap if it is even.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For book-img-for-question

Data Structures and Algorithm Analysis in Java

ISBN: 978-0132576277

3rd edition

Authors: Mark A. Weiss

See More Books

Question Posted: Mar 06, 2018 10:04 AM

See More Questions

Make the following modifications to your bannerads.html page so that it rotates the banner ads as opposed to selecting them at random. First, modify the opening BODY tag (line 22) so that it appears...
The following routine removes the first half of the list passed as a parameter:
a. What is the running time of Shellsort using the two-increment sequence {1, 2}? b. Show that for any N, there exists a three-increment sequence such that Shellsort runs in O(N5/3) time. c. Show...
Jerome Neeson is a shareholder in Gourmet Chefs Inc., a company that owns and operates a test kitchen in a large metropolitan area. The company is involved in a number of businesses, including...
Damping is negligible for a 0.150-kg object hanging from a light 6.30-N/m spring. A sinusoidal force with an amplitude of 1.70 N drives the system. At what frequency will the force make the object...
An engineer is studying the effect of cutting speed on the rate of metal removal in a machining operation. However, the rate of metal removal is also related to the hardness of the test specimen....
What is VTL?
Asset W has an expected return of 12.8 percent and a beta of 1.25. If the risk-free rate is 4.1 percent, complete the following table for portfolios of Asset W and a risk-free asset. Illustrate the...
A portfolio analyst has been asked to allocate investment funds among three different stocks. The relevant data for the stocks is shown in the following table. If the goal is to minimize risk while...
Putnam Company owns 80 percent of Swaraj Company. The excess of acquisition cost over book value was attributed entirely to previously unrecorded identifiable intangibles. For 2014, Swaraj Company...
Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5 using insertion sort.
Show how heapsort processes the input 142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102.
In a recent Super Bowl, a Nielsen report found that 45% of the 9,000 surveyed U.S. households had TV sets tuned to the game. The margin of error is 1 percentage point. a. Based on the given...
Explain the role of EHR healthcare technology in the delivery of care
In the movie, Money Ball what was the change that the Oakland A's was going through under the leadership of Billy Beane? 2.: In leading the change that you described in Q1, what was the...
Studies of the grapevine network within organizations have shown that the rumours and gossip on the grapevine are almost always accurate, and that a prudent manager is wise to act on that...
What is Program Evaluation? Describe What is need assessment? Describe? What is a program logic model? Describe and analyze. What is one example? (including input, output, short term outcomes and...
What are the primary jobs that must be performed at Spotify? Using the job characteristics theory as a frame-work, assess these jobs in terms of their motivating potential. 2. How does the concept of...
The number of bacteria in a certain culture grows exponentially. If 5,000 bacteria were initially present and 8,000 were present 10 minutes later, how long will it take for the number of bacteria to...
Drainee purchases direct materials each month. Its payment history shows that 65% is paid in the month of purchase with the remaining balance paid the month after purchase. Prepare a cash payment...
Professor Armstrong suggests the following procedure for generating a uniform random permutation: PERMUTE-BY-CYCLIC (A) 1 n length [A] 2 offset RANDOM (1, n) 3 for i 1 to n 4 do dest i + offset 5 if...
Explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. That is, your algorithm should produce a uniform random permutation, even...
What are the minimum and maximum numbers of elements in a heap of height h?
Suppose I have computed the cost of carbon per mile for my car at 0 . 0 1 2 per mile. Assume that the interest rate is 4 % and that I drive the car 2 8 , 0 0 0 miles per year. What is the present...
Imagine that in stable growth period, the firm earns ROIC of 10% and has after tax EBIT of 200 and reinvestment $ of 40. What is the steady state growth rate? 20% O 10% 2%
Tanner-UNF Corporation acquired as a long-term investment $160 million of 5.0% bonds, dated July 1, on July 1, 2021. Company management has the positive intent and ability to hold the bonds until...

Do either of the following modifications to the Shellsort routine coded in Figure 7.4 affect the worst-case

Question:

Step by Step Answer:

a No because it is still possible for consecut...View the full answer

Data Structures and Algorithm Analysis in Java

Students also viewed these Computer Sciences questions