Question

a) Use pseudocode to describe the algorithm that puts the first four terms of a list of real numbers of arbitrary length in increasing order using the insertion sort.

b) Show that this algorithm has time complexity \({\rm O}(1)\)in terms of the number of comparisons used.

Short answer

a) The required algorithm puts the arbitrary length in increasing order using the insertion sort is \({a_i}: = m\)

b) The algorithm has time complexity \({\rm O}(1)\) in the terms of the comparisons used.

Step-by-step solution

Writing pseudocode of the algorithm:

Consider natural numbers as \({a_1},{a_2},.....{a_n}\)

Procedure insertion sort- ( \({a_1},{a_2},.....{a_n}\): natural numbers with \(n \ge 2\))

\(\begin{array}{l}{\rm{for }}j: = 2{\rm{ }}to{\rm{ }}4\\i: = 1\\m: = {a_j}\\{\rm{for }}k = 0{\rm{ to }}j - i - 1\end{array}\)

\(\begin{array}{l}{a_{j - k}}: = {a_{j - k - 1}}\\{a_i}: = m({a_1},{a_2},....{a_n}{\rm{ is in increasing order}})\end{array}\)

Therefore, the required algorithm is \({a_i}: = m\)

Finding the time complexity:

The outer loop runs for 3-time steps

In the worst case, we consider that the list is in the increasing order

Thus, for each iteration of the outer loop, there will be a maximum of 2, 3 and 4 comparisons of the while loop (we are considering only the comparison operations).

Thus, it leads to a total of \(2 + 3 + 4 = 9\) comparisons.

Using the definition of complexity:

An algorithm is said to have \({\rm O}(1)\)or the constant complexity when accessing any single element in an array takes constant time as only one operation is to be performed to locate it.

Thus, the algorithm has time complexity \({\rm O}(1)\)in terms of the number of comparisons used.