Count the specific amount of steps in a sorting algorithm with given pseudo code

Question

I need to count the specific amount of steps which are used by sorting algorithm pseudo code.

---

Here are some guide lines given:

• a:=1 is considered 1 step
• a:= b + c is 1 step
• a:= b + c - d is 2 steps
• A[i+j] = a + b is 2 steps
• for i := 1 to k do is k(2+1) steps

---

My given code is as follows

A[1 ; n]

1//m := n - 1
2//for i := 1 to m do
3//   min := A[i]
4//   k := i
5//   for j := i + 1 to n do
6//       if A[j] < min then
7//           min := A[j]
8//           k := j
9//   A[k] := A[i]
10//  A[i] := min

I marked the lines of the code because I have quite a few of them figured out, however I need some help with some of them.

1// 1 step

2// 2(m+1) = 2n

3// m = n-1

4// m = n-1

5// $\sum_{j=2}^n j$ + 2(n-1) I am not sure about this one.

6// $\sum_{j=2}^n j$ I am not sure about this one as well.

I really can't figure out how many steps the 7th or 8th lines should be.

9// m = n-1

10// m = n-1

I really need help with lines 5-8 because I can figure out how many steps these of code these lines would take.

Thank you in advance for the help!

Answer 1

The outer $\texttt{for}$ loop

for i := 1 to m do

amounts to \begin{align*} 2\sum_{i=1}^m 1+2=2m+2 \end{align*} operations.

---

The inner $\texttt{for}$ loop

for j := i+1 to n do

amounts to \begin{align*} 2\sum_{j=i+1}^n 1+2&=2\sum_{j=1}^{n-i} 1+2\\ &=2(n-i)+2=2(n-i+1)\tag{1} \end{align*} operations.

---

Both $\texttt{for}$ loops

for i := 1 to m do
    for j := i+1 to n do

amount according to (1) to \begin{align*} \color{blue}{2\sum_{i=1}^m}&\color{blue}{\left(2\sum_{j=i+1}^n 1+2\right)+2}\\ &=2\sum_{i=1}^m2\left(n-i+1\right)+2\\ &=4n\sum_{i=1}^m 1 - 4\sum_{i=1}^m i+4\sum_{i=1}^m 1+2\\ &=4nm-4\frac{m(m+1)}{2}+4m+2\\ &\,\,\color{blue}{=2m(2n-m+1)+2} \end{align*} operations.