Activity $4\mathrm{.}5\mathrm{.}2$: Selection Sort

Consider the following algorithm on an array of numbers x$1,$ x$2,$ x$3,...,$ xn$.$

The element in the first position is compared to the n $1$ remaining elements; whenever one is found that is less, the first element is swapped with it$.$ Then the element in the second position is compared with the remaining n $2$ elements. Whenever one is found that is less, the elements are swapped. This continues until the $($n$1)$st element; if it is out of order with the nth element, the elements are swapped. The algorithm pseudocode is shown below:

The selection sort algorithm

Step through this algorithm when applied to the array x$1=9,$ x$2=4,$ x$3=7,$ x$4=1.$ Record the values of the array every time they change.

In terms of n$,$ how many comparisons does this algorithm make on an array of length n$?$

Activity $4\mathrm{.}6\mathrm{.}2$: Big$-$O Notation

Let g$($n$)=7$n $+90$ and f$($n$)=2$n$.$

Suppose K $=3.$ Is there a value of N $>0$ such that g$($n$)<=$ K f $($n$)$ for all n $>=$ N $?$ If so$,$ what value works? If no such value exists, explain why.

Suppose K $=5.$ Is there a value of N $>0$ such that g$($n$)<=$ K f $($n$)$ for all n $>=$ N $?$ If so$,$ what value works? If no such value exists, explain why.

Is g $$ O$($f$)?$ Justify your answer using the definition.

Let g$($n$)=3$n$2+100.$ Use the definition to show that g $$ O$($n$2).$ Specifically, find values of K and N that satisfy the definition, where f$($n$)=$ n$2.$

Let g$($n$)=$ n$3.$ Prove, by contradiction, that g $$ O$($n$2),$ by completing the following steps.

Suppose, to the contrary, that g in O$($n$2).$ Then the definition of big$-$O says that there are numbers K and N and an inequality involving K and n that must hold for all n $>=$ N $.$ Write this inequality.

Explain why the above inequality leads to a contradiction.