Discrete Mathematics for Computer Science

326 CHAPTER^5 Analysis of Algorithms

6. The code that follows implements Homer's algorithm for evaluating polynomials. Find
   its complexity, assuming multiplication is the key operation. Here, the phrase "for i ...
   down to 0" down to means to subtract^1 each time through the loop until i < 0.

Evaluate P(x) = ao + a Ix + a2x 2 + •••+ an Xn at x0

INPUT: n E N and a real number x0 and the coefficients of a polynomial of degree n

stored in a[.O. n]

OUTPUT: P(xo)

Poly =xo .a[n] + a[n -1]

for i = n - 2 down to 0

Poly = Poly .xo + a[i]

print Poly

7. The Insertion Sort algorithm that follows is a good sorting algorithm to use when (i) the
   size of the list is very small (say, <10) or (ii) the list is already almost in order. In this
   respect, it is like bubblesort, but it is normally a bit better.
   Calculate the complexity of the Insertion Sort algorithm on an input List of size
   N. Let comparison of list elements be the key operation. (Hint: For this version, which
   sorts the list into increasing order, the worst-case behavior occurs when the list is in
   decreasing order.)

INPUT: A list List of values, List[] 11,. List[N]

OUTPUT: The same elements, but in increasing order

for positionToFix = 2 to N do

valueToPlace = List[positionToFix]

candidatePos = positionToFix

/* locate place to put valueToPlace, */

/* relative to previous elements, */

/* and open up room to insert it there.*/

while candidatePos > 1 and List[candidatePos - 1] > valueToPlace

List[candidatePos] = List[candidatePos - 1]

candidatePos = candidatePos - I

List[candidatePos] = valueToPlace