On average each insertion must traverse half the currently sorted list while making one comparison per step. The list grows by one each time.

So starting with a list of length 1 and inserting the first item to get a list of length 2, we have average an traversal of .5 (0 or 1) places. The rest are 1.5 (0, 1, or 2 place), 2.5, 3.5, ... , n-.5 for a list of length n+1.

This is, by simple algebra, 1 + 2 + 3 + ... + n - n*.5 = (n(n+1) - n)/2 = n^2 / 2 = O(n^2)

Note that this is the average case. In the worst case the list must be fully traversed (you are always inserting the next-smallest item into the ascending list). Then you have 1 + 2 + ... n, which is still O(n^2).

In the best case you find the insertion point at the top element with one comparsion, so you have 1+1+1+ (n times) = O(n).

At first, this does not seem to be a proper code for insertion sort. It seems that you are using bubble sort code in reverse manner.
In an insertion sort code you don't replace a small element with every large element that falls before it, rather we skim through all the large elements that fall before it and only when we are at the point where there are no elements left or there is no more large element, then we place the small element at that place and shift/move all other succeeding elements.

As a part for O(n) time:
Lets consider an array of five already sorted elements - arr[11,13,15,17,19]. We move from first position element to last position.
Step 1: Take element 11, as it is first element we keep it as it is.
Step 2: Take element 13, look for element that falls before it(that is element 11), as 13>11, therefore no further need for looking at elements that fall before 11.
Step 3: Take element 15, look for element that falls before it(that is element 13), as 15>13, therefore no further need for looking at elements that fall before 13.
Step 4: Take element 17, look for element that falls before it(that is element 15), as 17>15, therefore no further need for looking at elements that fall before 15.
Step 5: Take element 19, look for element that falls before it(that is element 17), as 19>17, therefore no further need for looking at elements that fall before 17.

As we see that for five already sorted elements we required only 5 comparisons, thus for 'n' sorted elements we require only O(n) comparisons.

I hope above example clarifies your doubt.

To answer this question, let's first determine how we can evaluate the runtime of insertion sort. If we can find a nice mathematical expression for the runtime, we can then manipulate that expression to determine the average runtime.

The key observation we need to have is that the runtime of insertion sort is closely related to the number of inversions 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 Θ(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 Θ(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 Θ(n + 0) = Θ(n), and in a reverse-sorted array, there are n(n - 1)/2 inversions, and the runtime is Θ(n + n(n-1)/2) = Θ(n²). 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 = Σ Xij

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

E[I] = E[Σ Xij] = Σ 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] = ΣE[Xij] = Σ (1 / 2)

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

E[I] = n(n - 1) / 4 = Θ(n²)

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

Hope this helps!

The wording relates to probabilities of the positioning of elements in the initial order, not the state where $a_1, \dots,a_{j-1}$ are already sorted. It simply means the elements are randomly ordered. I would suggest defining $p_j(k)$ this way is not very helpful. You could equivalently define it to be the probability that $a_j$ is the $k$th largest of $a_1, \dots, a_j$. That then relates directly to the rest of the paragraph.

In short, the worst case is when your list is in the exact opposite order you need. In that case:

• For the first item, you make 0 comparisons, of course.
• For the second item, you compare it to the first item and find that they are not in the right position; you've made 1 comparison.
• For the third, you compare it with both, and find that the third has to go to the top. You've made 2 comparisons.
• This goes on; for every following value, you make one more comparison.
• Finally, for the nth item, you make n - 1 comparisons.

If you add up the number of comparisons you make for the worst case, you'll see that it is 0 + 1 + 2 + ... + n-1, which is equal to (n^2 - n) / 2 comparisons for the worst case, which is O(n^2). (The part that determines the complexity is when we consider large n, in which case the n^2 term dominates)