Introduction to Discrete Mathematics
Quiz No. 4
April 4, 2008

Name:                                                                                                Grade:                                

1. True or False (25 points)
a. ____ If f(n) is O(g(n)) and g(n) is O(h(n)), then h(n) is O(f(n))
b. ____ The function an^k is O(n^k)
c. ____ If f(n) = cg(n), then f(n) is O(g(c))
d. ____ If f(n) is O(h(n)) and g(n) is O(h(n)), then h(n) is O(f(n)+g(n))
e. ____ The function nk  is O(nk+j) for any positive j

2. Given f(n) = 3n² + n + 5
    Determine which of the following functions is a candidate for g(n), as in f(n) ≤ Cg(n)? Show work for each. (15 points)
    a. g(n) = 5
    b. g(n) = n
    c. g(n) = n²

3. The following algorithm can be used to determine all prime numbers less than or equal to n. For the algorithm (outer for loop), determine appropriate pre- and post-conditions, and a loop invariant. Show how these assertions prove the correctness of the algorithm.
(60 points)

num := 0
for x = 2 to n
        prime := true
        for i = 1 to num
                if (x mod prime[i]) > 0 then
                    prime := false
                end if
        next
        if prime then
                num := num + 1
                prime[num] := x
        end if
next