Math 2320 -- Quiz 1 D -- Dow -- September 30, 2:00

    1. (4marks) Using the definition of "f(n) is O(g(n))"
      show that " if f(n) is O(3n^2+16) then f(n) is O(n^2) .

      (2marks) for somehow stating the definition of "f(n) is O(g(n)) " being sure to mention C and k.
      From the definition, we've got that
      |f(n)| < C*(3n^2+16) for all n > k for some C and k.

      (1mark) Then we just note that 3n^2+16 < 4 n^2 for all n> 4 (or some such similar thing).

      (1mark) Hence, |f(n)| < C'* n^2 for all n> k' where C'=4C and k' is bigger than both k and 4 (or whatever value you used above).

    2. State whether this is True or False ?
      If f(n) is O(n^2) then f(100) is bigger than f(10) .

      If true, give an example. If false, give a counterexample.

    It is false, f(n) being the constant function 1 or some used f(n)=1/n are counterexamples.

  1. 2. In the following algorithm t will count the number of critical steps.
    Procedure Sum_of_2 (x,a_1,a_2,...,a_n; n integers)
    t:=1 { this is our counting device}}
    i:=1
    while i <= n
    begin
    j:=i { j starts at i }
    t:=t+1 { t {\rm is just the counter }}
    while a_i+a_j <> x and j <= n
    begin
    t:=t+1 { t is just the counter }
    j:=j+1
    end { end the while}
    if j <= n { test if they were equal }
    then i:=n+2 { make i large if x=a_i+a_j }
    else i:=i+1 { usual increment otherwise }
    t:=t+2 { increment counter (by 2 to see if you're watching)}
    end {the i loop ends here}
    { i is n+2 if x was equal to some a_i+a_j }
    (a) What is the value of the counter t as a function of n in the worst case? [A sum of terms is an acceptable answer for part (a).]

    (2marks) for some reasonable looking sum that showed that you analyzed the algorithm for each value of i as i runs from 1 to n.

    Considering some fixed i between 1 and n, we see that j starts at i and runs up to potentially n, hence j runs through n-i+1 values.

    What happens to t while all this is going on? Well, for each i, we increment t by 1 before we start the j loop and increment it by 2 when we finish the j loop. During the j loop, we increment by 1 for each value of j, Hence 3+(n-i+1) times.

    Answer: (3+n)+(3+(n-1))+(3+(n-2))+...+(3+(n-(n-1)))
    or 3n + (n+(n-1)+(n-2)+...+2+1).

    Marks: (1mark) for a reasonable looking sum, and (1mark) for having either the "n-i" or the " +2" show up.

    (b) What is the time complexity, as calculated by t, in the worst case?

    Of course that expression in Part (a) is O(n^2).