The general formula of polynomial function is p(n)= where is constant and >0.

• In order to express the polynomial function in terms of notation, identify the term, which is having the highest power and ignore the coefficients of the term.

• The highest term in the general formula of polynomial function is .

• Therefore, the notation of general polynomial function will be

The given polynomial function is .

• The terms in the polynomial are ,, and 3.

• The highest term in the given polynomial function is .

• Therefore, the notation of given polynomial function

Hence, the notation of the function is .

Loop invariants:

After each iteration, the element at the position index is properly placed. The array is divided into two subarrays.

• The first subarray A [1...index] will contain the index smallest elements arranged in increasing order.

• The second subarray A [index+1...n] will contain the elements to be sorted.

Reason to run only for first n-1 elements:

• In the first iteration, the smallest element in the list A[1..n] is found and is exchanged with the element at first position.

• In the second iteration, the smallest element in the list A[2..n] is found and is exchanged with the element at second position.

• In the third iteration, the smallest element in the list A[2..n] is found and is exchanged with the element at third position.

• The process continues for all the elements until there are only 2 elements left to be sorted.

• In the n-1 iteration, there will be only two elements in the list. The smallest element in the list A [n-1, n] is found and is exchanged with the element at n-1 position.

• The last element A[n] is already placed in its proper position. Therefore, there is no necessity for executing the loop.

Hence, the loop runs for first n-1 elements rather than for all n elements.

Best-case and worst-case running times:

In selection sort algorithm, the entire unsorted list must be searched to find the minimum element.

In the iteration, the inner loop executes exactly times, and on each such execution exactly one array comparison is performed.

Thus, in all cases (best, worst, average) the number of comparisons done by Selection Sort is

Therefore, the run time of Selection Sort is in all cases.

Pseudo code for Linear Search

// pseudo code for linear search scans the sequence for v using a loop invariant:

Input: A sequence of n numbers and a value v.

Output: An index i such that v = A[i] or the special NIL if v does not appear in A.

Linear Search (A, v)

1. for i =1 to n

2. {

3 if A[i] = v

4. return i

5. }

6. return NIL

Average case:

Average case occurs when the element to be searched is found in the array. In such a case, the linear search will search through half of the array.

Thus, the number of elements that are searched on an average is n/2.

Hence, the running time of linear search in the average case is .

Worst Case:

Worst case occurs when the element to be searched is the last element in the array or may not be there in the array. In such a case, the entire array needs to be searched.

Thus, the number of elements that are searched in a worst case is n.

Hence, the running time of linear search in the worst case is .

To have a good best-case running time, choose a particular instance of the input and pre-compute its output.

• In the beginning of the algorithm, first check if the given input is same as the input for which the output has been pre-computed.

• If so, just provide the pre-computed output as output.

This will make the algorithm to have good best-case running time.