MATH 302 Lecture 1

« previous | Monday, August 29, 2011 | next »

Algorithms

Simple Searching & Sorting examples:

Max element in List

procedure max ([a_1, ..., a_n] : integers):

   max := a_1
   for i = 2..n:
       if max < i then:
           max := a_i
       end if
   end for
   return max

end procedure

Performs $n-1=O(n)$ comparisons

Linear Search

procedure linear search (x : integer, [a_1, ..., a_n] : distinct integers)

   i := 1
   while i <= n and x != a_i:
       i := i + 1
   end while
   if i <= n then:
       location := i
   else:
       location := 0
   end if
   return location

end procedure

Asymptotic Analysis describes growth of functions