Jess: Data Structures, Week 7

7.2 What is the running time of insertion sort if all elements are equal?O(n) is best case

7.10 Do either of the following modifications to the Shellsort routine coded in Figure 7.4 affect the worst-case running time?
a. Before line 11, subtract one from gap if it is even.
No, because it is still possible for consecutive increments to share a common factor. An example is the sequence 1, 3, 9, 21, 45, ht+1 = 2ht + 3.

b. Before line 11, add one to gap if it is even.
Yes, because consecutive increments are relatively prime. The running time becomes O(N^(3/2)).

7.11 Show how heapsort processes the input 142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102.

Then turn it in to maximum heap:

7.12 What is the running time of heapsort for presorted input?
O(N log N)