Chapter 8 Answers

• Ω(n) to examine all the input.
  • Question 8.1 - What does that mean? All input must be examined to determine the lower bound - when already sorted.

• Question 8.2 - We proved Θ(n lg n) for merge and heap sort.
  • What is the basic argument for merge sort? The height of the recursion tree is lg n - the cost of dividing the problem to size 1 - the merge cost is n.
  • What is the basic argument for heap sort? All n maximum elements at index 1 are exchanged to the last index of heap - Max_Heapify, a lg n operation, is performed on element at index 1 to restore max-heap property.

Question 8.3

Would the following produce the same results? Yes

Would the following produce the same decision tree, that is, the same number of comparisons? Yes

Diagram the left decision tree. Same as in notes.

Bubble sort

Question 8.4

• Guess (estimate) the worst and best case run time. O(n²)
   
• Is the sort ascending or descending? Ascending - the larger value is moved to higher index.

Comparisons

(n-1) + (n-2) + ... + 2 + 1 = n*(n-1) / 2

Question 8.5 - Worst case order? O(n²)

Sort on 3 elements A[1], A[2] and A[3]

Question 8.6

How many possible results (leaves) are there for sorting 3 elements? Count them. 6

What function of n=3 gives that result? 3*2*1=6. That is f(n) = n!

What would be the number of leaves for n=5? 120

What is P(n, n)?    n!/(n-n)! = n!

What is a good guess for the height of the binary decision tree for sorting n elements? lg n!

Insertion sort

Question 8.7 - Which of the following analyses represent the best and the worst cases? Best then worst.

When does each occur?  No insertion: c₅ is O(n) and no c₆ and c₇ occur. When an insertion made, c₅, c₆ and c₇ - are O(n²) operations.

T(n) = c₁n + c₂(n-1) + c₄(n-1) + c₅(n-1) + c₈(n-1)     

       = (c₁+ c₂ + c₄ + c₅ + c₈)n - (c₂ + c₄ + c₅ + c₈)

       = an + b for some a and b constants

          = an² + bn + c for some constants a, b and c

Bounding sorts Ω(n lg n) and O(n lg n)

Question 8.8

• What does Any binary comparison sort of n elements requires Ω(n lg n) comparisons in the worst case really mean? The fewest number of comparisons for an unsorted list.

• Can we get lucky and do better? Only n comparisons to determine the list is sorted, but not to sort. worse? Remember the bubble sort, it was the same whether sorted or not, O(n²).