Question

Consider insertsort. Suppose that the input array A has 1% probability to be monotonically decreasing. Show...

Consider insertsort. Suppose that the input array A has 1% probability to be monotonically decreasing. Show that, in this case, the average-case complexity of insertsort is Θ(n^2).

Homework Answers

Answer #1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

The key observation we need to have is that the runtime of insertion sort is closely related to the number ofinversions in the input array. An inversion in an array is a pair of elements A[i] and A[j] that are in the wrong relative order - that is, i < j, but A[j] < A[i]. For example, in this array:

0 1 3 2 4 5

There is one inversion: the 3 and 2 should be switched. In this array:

4 1 0 3 2

There are 6 inversions:

  • 4 and 1
  • 4 and 0
  • 4 and 3
  • 4 and 2
  • 1 and 0
  • 3 and 2

One important property of inversions is that a sorted array has no inversions in it, since every element should be smaller than everything coming after it and larger than everything coming before it.

The reason this is significant is that there is a direct link between the amount of work done in insertion sort and the number of inversions in the original array. To see this, let's review some quick pseudocode for insertion sort:

  • For i = 2 .. n: (Assuming 1-indexing)
    • Set j = i - 1.
    • While A[j] > A[j + 1]:
      • Swap A[j] and A[j + 1].
      • Set j = j - 1.

Normally, when determining the total amount of work done by a function like this, we could determine the maximum amount of work done by the inner loop, then multiply it by the number of iterations of the outer loop. This will give an upper bound, but not necessarily a tight bound. A better way to account for the total work done is to recognize that there are two different sources of work:

  • The outer loop, which counts 2, 3, ..., n, and
  • The inner loop, which performs swaps.

That outer loop always does theta(n) work. The inner loop, however, does an amount of work that's proportional to the total number of swaps made across the entire runtime of the algorithm. To see how much work that loop will do, we will need to determine how many total swaps are made across all iterations of the algorithm.

This is where inversions come in. Notice that when insertion sort runs, it always swaps adjacent elements in the array, and it only swaps the two elements if they form an inversion. So what happens to the total number of inversions in the array after we perform a swap? Well, graphically, we have this:

 [---- X ----] A[j] A[j+1] [---- Y ----]

Here, X is the part of the array coming before the swapped pair and Y is the part of the array coming after the swapped pair.

Let's suppose that we swap A[j] and A[j+1]. What happens to the number of inversions? Well, let's consider some arbitrary inversion between two elements. There are 6 possibilities:

  • Both elements are in X, or both elements are in Y, or one element is in X and one element is in Y. Then the inversion is still there, since we didn't move any of those elements.
  • One element is in X or Y and the other is either A[j] or A[j+1]. Then the inversion is still there, since the relative orderings of the elements haven't changed, even though their absolute positions might have.
  • One element is A[j] and the other A[j+1]. Then the inversion is removed after the swap.

This means that after performing a swap, we decrease the number of inversions by exactly one, because only the inversion of the adjacent pair has disappeared. This is hugely important for the following reason: If we start off with I inversions, each swap will decrease the number by exactly one. Once no inversions are left, no more swaps are performed. Therefore, the number of swaps equals the number of inversions!

Given this, we can accurately express the runtime of insertion sort as theta(n + I), where I is the number of inversions of the original array. This matches our original runtime bounds - in a sorted array, there are 0 inversions, and the runtime is theta(n + 0) = theta(n), and in a reverse-sorted array, there are n(n - 1)/2 inversions, and the runtime is theta(n + n(n-1)/2) = theta(n^2). Nifty!

So now we have a super precise way of analyzing the runtime of insertion sort given a particular array. Let's see how we can analyze its average runtime. To do this, we'll need to make an assumption about the distribution of the inputs. Since insertion sort is a comparison-based sorting algorithm, the actual values of the input array don't actually matter; only their relative ordering actually matters. In what follows, I'm going to assume that all the array elements are distinct, though if this isn't the case the analysis doesn't change all that much. I'll point out where things go off-script when we get there.

To solve this problem, we're going to introduce a bunch of indicator variables of the form Xij, where Xij is a random variable that is 1 if A[i] and A[j] form an inversion and 0 otherwise. There will be n(n - 1)/2 of these variables, one for each distinct pair of elements. Note that these variables account for each possible inversion in the array.

Given these X's, we can define a new random variable I that is equal to the total number of inversions in the array. This will be given by the sum of the X's:

I = k(Xij

We're interested in E[I], the expected number of inversions in the array. Using linearity of expectation, this is

E[I] = E[k*Xij] = k*E[Xij]

So now if we can get the value of E[Xij], we can determine the expected number of inversions and, therefore, the expected runtime!

Fortunately, since all the Xij's are binary indicator variables, we have that

E[Xij] = Pr[Xij = 1] = Pr[A[i] and A[j] are an inversion]

So what's the probability, given a random input array with no duplicates, that A[i] and A[j] are an inversion? Well, half the time, A[i] will be less than A[j], and the other half of the time A[i] will be greater than A[j]. (If duplicates are allowed, there's a sneaky extra term to handle duplicates, but we'll ignore that for now). Consequently, the probability that there's an inversion between A[i] and A[j] is 1 / 2. Therefore:

E[I] = kE[Xij] = theta (1 / 2)

Since there are n(n - 1)/2 terms in the sum, this works out to

E[I] = n(n - 1) / 4 = theta(n^2)

And so, on expectation, there will be theta(n^2) inversions, so on expectation the runtime will be theta(n^2 + n) =theta(n^2). This explains why the average-case behavior of insertion sort is theta(n^2).

Kindly revert for any queries

Thanks.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Find the worst-case complexity of the algorithm below. Show your work. UFSizeCalc Input:  uf: Union-Find array of...
Find the worst-case complexity of the algorithm below. Show your work. UFSizeCalc Input:  uf: Union-Find array of size n Input: n: size of uf Output: size array for uf; that is, an array s such that s[r] equals the number of elements in the Union-Find tree rooted at r, for every root r (s may have any value for indexes that are not roots of uf) Pseudocode: For i = 1 to n uf.Find(i) size = Array(n) Initialize size to be...
2.) Consider an input array A of size n in which n − 1 of the...
2.) Consider an input array A of size n in which n − 1 of the elements have identical values and the remaining one value is smaller than the n − 1 identical values. What is the running time of Heapsort with input A?
Let Sum from n=1 to infinity (an) be a convergent series with monotonically decreasing positive terms....
Let Sum from n=1 to infinity (an) be a convergent series with monotonically decreasing positive terms. Prove that limn→∞ n(an) = 0.
Suppose the probability of obtaining a score between 0 and 100 on an test increases monotonically...
Suppose the probability of obtaining a score between 0 and 100 on an test increases monotonically between 0 and 1.00. Is the average score on the test (a) greater than 50, (b) equal to 50, (c) less than 50 ?
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1]...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n = 1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1] return temp else return T[n − 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.
Let A[1, . . . , n] be an array of n distinct numbers. If i...
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. 1. Which arrays with distinct elements from the set {1, 2, . . . , n} have the smallest and the largest number of inversions and why? State the expressions exactly in terms of n. 2. For any 0 < a < 1/2, construct an array for...
1. Given β = XT 1×nAn×nXn×1, show that the gradient of β with respect to X...
1. Given β = XT 1×nAn×nXn×1, show that the gradient of β with respect to X has the following form: ∇β = X T (A + A T ). Also, simplify the above result when A is symmetric. (Hint: β can be written as Pn j=1 Pn i=1 aijxixj ). 2. In this problem, we consider a probabilistic view of linear regression y (i) = θ T x (i)+ (i) , i = 1, . . . , n, which...
Suppose an array A stores n integers, each of which is in {0, 1, 2, ...,...
Suppose an array A stores n integers, each of which is in {0, 1, 2, ..., 99}. Which of the following sorting algorithms can sort A in O(n) time in the worst case? Question 16 options: A) merge sort B) counting sort C) quicksort D) None of these options is correct. E) insertion sort
1) Suppose an algorithm has 6 types of input given by S = {I_1, I_2, ...,...
1) Suppose an algorithm has 6 types of input given by S = {I_1, I_2, ..., I_6}. Suppose the inputs occur with the following probabilities:   P(I_2) = P(I_3) = P(I_4) = 1/12, P(I_5) = P(I_6) = 1/6, and P(I_1) = 5/12. Suppose further that each input "I_n" (n = 1,2,3,4,5,6) causes the algorithm to execute "5n" instructions. What is the expected number of instructions executed by the algorithm? 2) When three fair dice are tossed, what is the probability that...
Selection-Sort( A[1..n] ) 1 2 3 4 5 6 7 8 9 10 // INPUT: A[1..n],...
Selection-Sort( A[1..n] ) 1 2 3 4 5 6 7 8 9 10 // INPUT: A[1..n], an array of any n numbers in unknown order integer i, j, m fori=1ton−1 do swap A[i] ↔ A[m] // OUTPUT: A[1..n], its numbers now sorted in non-decreasing order m=i for j = i to n do if A[j] < A[m] then m = j Give a proof that this algorithm sorts its input as claimed.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT