Skip to content

2.2 Analyzing algorithms

2.2-1

Express the function $n^3/1000+100n^2-100n+3$ in terms of $\Theta$-notaion.

$\Theta (n^3)$

2.2-2

Consider sorting $n$ numbers stored in array $A[1:n]$ by first finding the smallest element of $A[1:n]$ and exchanging it with the element in $A[1]$. Then find the smallest element of $A[2:n]$, and exchange it with $A[2]$. Then find the smallest element of $A[3:n]$, and exchange it with $A[3]$. Continue in this manner for the first $n-1$ elements of $A$. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first $n-1$ elements, rather than for all $n$ elements? Give the worst-case running time of selection sort in $\Theta$-notation. Is the best-case running time any better?

  • pseudocode
SELECTION_SORT(A)
    for i = 1 to A.length()-1
        minindex = i
        for j = i to A.length()
            if A[j]<A[minindex]
                minindex = j
        swap(A[i],A[minindex])
  • loop invariant: At the start of $i$th iteration, $A[1:i-1]$ consist of the $i-1$ elements of $A[1:n]$ and it is at sort order.
  • When the i-1 smallest elements are sort in the subarray $A[1:n-1], the biggest element must be $A[n]$, and then A[1:n] are sort.
  • worse case: in each iteration, $j$ increase from $i$ to $n$, $running time = (n) + (n-1) + ... + (2) = \Theta (n^2)$
  • best case: the same as worst case since in each iteration in inner for loop, j must go from i to n to get the minindex.

2.2-3

Consider linear search again (see Exercise 2.1-4). How many elements of the input array need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case?

Using $\Theta$-notation, give the average-case and worst-case running times of linear search. Justify your answers.

  • average-case: $\text{running time}\sum_{i=1}^{n} i/n = (n+1)/2 = \Theta(n)$
  • worst-case: $\text{running time} = n =\Theta(n)$

2.2-4

How can you modify any sorting algorithm to have a good best-case running time

modidy combine with insertion sort ,such as check whether each element in array is smaller(bigger) than the righthand element, since it produce a best - case running time of $\Theta(n)$, the same as travel throught the array, which is a neccessary step for sorting.