# Question: The next two parts will prove inequality 2 3 b State

The next two parts will prove inequality (2.3).

b. State precisely a loop invariant for the for loop in lines 2-4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter.

c. Using the termination condition of the loop invariant proved in part (b), state a loop invariant for the for loop in lines 1-4 that will allow you to prove inequality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter.

d. What is the worst-case running time of bubble sort? How does it compare to the running time of insertion sort?

b. State precisely a loop invariant for the for loop in lines 2-4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter.

c. Using the termination condition of the loop invariant proved in part (b), state a loop invariant for the for loop in lines 1-4 that will allow you to prove inequality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter.

d. What is the worst-case running time of bubble sort? How does it compare to the running time of insertion sort?

## Answer to relevant Questions

Let A[1 ¬ n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. a. List the five inversions of the array ¬2, 3, 8, 6, 1¬. b. What array with elements from the ...The procedure BUILD-MAX-HEAP in Section 6.3 can be implemented by repeatedly using MAX-HEAP-INSERT to insert the elements into the heap. Consider the following implementation: BUILD-MAX-HEAP'(A) 1 heap-size [A] ← ...For n distinct elements x1, x2, ..., xn with positive weights w1, w2, ..., wn such that Σni =1 wi = 1, the weighted (lower) median is the element xk satisfying a. Argue that the median of x1, x2, ..., xn is the ...The Euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects a given set of n points in the plane. Figure 15.9(a) shows the solution to a 7- point problem. The general problem ...Suppose that you are given an n × n checkerboard and a checker. You must move the checker from the bottom edge of the board to the top edge of the board according to the following rule. At each step you may move the checker ...Post your question