insertion sort basic computation steps

Question

Here is insertion sort:

for i = 1 to length(A)
 x = A[i]
 j = i - 1
 while j >= 0 and A[j] > x
 A[j+1] = A[j]
 j = j-1
 end while
 A[j+1] = x
end for

My lecture notes say that the total number of basic computation steps is about

$$T = 1 + ( 5 + t_1 \times 3 ) + \dots + ( 5 + t_{n-1} \times 3 ),,円$$

where $t_i$ represents how many times the inner loop needs to run (anything between 0ドル$ and $i$). 5ドル$ for the basic operations in the outer loop, and 1ドル$ for testing whether to enter the outer loop.

I understand the "1" and the "5" but not the "3". Because I think $t_i$ is not always anything between 0ドル$ and $i$? Like say a number needs to move from position 5ドル$ to position 1ドル,ドル it repeats the inner loop meaning there will be more steps? The steps in the inner loop can possibly repeat for $n-1$ times?

So what is the basic computation steps?

• D.W.: Welcome to CS.SE! Please edit the question to provide a self-contained definition for all notation. What does "x 3" represent? Could that potentially have been "x_3"? If so, what does that variable represent? Have you tried reading any other book's analysis of insertion sort? The running time of insertion sort is explained in many places; you might want to start by reading another reference and understanding it, then come back to your particular lecture notes.
• lalala: x 3 means *3. and I have tried other analysis and I just don't understand. Basically the question is: when trying to move a number across 4 positions (Shifting), the while loop must be implement 4 times? Because it needs to compare the value with the key for 4 times until the previous key is smaller than the value?
• Raphael: Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
• Raphael: "So what is the basic computation steps?" -- you need to be more precise. Are you meaning to ask "what is the number of ... executed in the worst case"? If not, what is it?

Answer 1

You asked why the "3" is there in that equation. Here's the explanation.

$t_i$ counts the number of iterations of the inner loop, for a particular value of $i$. Each iteration executes 3 instructions (3 steps). Therefore, the total number steps of computations consumed by the inner loop, for a particular value of $i,ドル is 3ドル \times t_i$.

Answer 2

I believe to make it easy to understand it is necessary to set it as a task. So here it is:

TASK: Insertion Sort INPUT: $a_{1}, a_{2},...,a_{n} \in {\rm I\!R}\ or\ {\rm I\!N} $

OUTPUT: $b_{1}, b_{2},...,b_{n}$ the $a_{i}s $ in increasing order.

Insertion sort algorithm solves above task as follows. On the first iteration we have the sequence $a_{1},...,a_{n}.$ On the $j^{th}$ iteration we have the sequence $c_{1},...,c_{j},a_{j+1},...,a_{n}$. Note that $c_{1},...,c_{j}$ are the numbers $a_{1},...,a_{j}$ in increasing order. Trivially, on the first iteration $c_{1}=a_{1}$ and on the last we have sorted list of numbers.

So to construct $c_{1},...,c_{j},c_{j+1},a_{j+2},...,a_{n}$ from the previous iteration $c_{1},...,c_{j},a_{j+1},...,a_{n}$ we do the following;

compare $a_{j+1}$ with $c_{j},c_{j-1},...$ in this order and stop when its place is found. That is when $c_{i} < a_{j+1} <= c_{i+1}$. We then insert that $a_{j+1}$ between. When $a_{j+1} < c_{j}$ then $a_{j+1}$ becomes the first element on the next iteration, and when $a_{j+1} > c_{j}$ then $c_{j+1} = a_{j+1}$ and there are no more comparisons required.

So to find the new place for $a_{j+1}$ and to complete the $j^{th}$ iteration it takes at most j comparisons. So the total number of iterations is at most $ \sum^{n-1}_{j=1}j = n(n-1)/2 = O(n^2).$ Thus we end up with a conclusion that the complexity of the Insertion sort algorithm is $T(n) = n(n-1)/2$.

Hopefully this will help you understand the pseudo code above a bit better. I know from my experience as a Computer Scientist that these can be unclear at the start.

• marcincuber: And yes as @D.W. mentioned I would also recommend learning at least basics of LaTex or Tex, it is helpful in many scenarios.