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

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

      (2marks) give the definition (in some form) of f(n) is O(g(n)), being sure to mention the C and the k.

      (2marks) By definition, there are C,k such that
      |f(n)| < C*(2n^2) for all n> k

      Therefore if we use c=2C and keep k in the definition, we get that
      |f(n)|< c*|n^2| for all n> k
      as required.

    2. State whether this is True or False?

      If f(n) is O(n^2) then n^2 is O(f(n)).

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

    3. This is false, and f(n)=n is the kind of counter-example we'd expect (even f(n)=1 for all n works).

    4. In the following algorithm t is just used as a counting device.
      Procedure Divisors (n ; a positive integer)
      d:=0 {d will count the number of divisors }
      t:=0  { t is the counting device
      for i:=1 to n
      begin
       k:= i
       while  k+i < n { testing i}
      begin
       k:=k+i { k increments by i }
       t:= t+1 { t counts the number of basic steps }
       end
       if k+i=n then d:= d+1 { Check to see if i divides n }
       end
       {d will be the number of positive integer divisors of n}

      (a) What is the value of the counter t as a function of n?

      [A sum of terms is an acceptable answer for part (a).]

      I expected something like:
      Consider one by one, each value of i. i will go from 1 to n.
      If i=1, then the next while loops exactly n-1 times.
      If i=2, it loops [n/2]-1 times because k is incrementing by 2's up to at most (n-1).
      In general, for a fixed value of i, the k while loop, runs [n/2]-1 times.
      For values of i bigger than n/2 it doesn't loop at all.

      Therefore we get the expression:
      (n-1) + ([n/2]-1) + ... + ([n/i]-1) + ... + 0 + 0

      We can add up the -1's, to get (n+[n/2]+[n/3]+...+[n/n])-n.

      If you didn't catch the [n/i] idea, but at least realized it was no more than n-i (since the looping starts at i you still get full marks (carrying the "error").

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

      [If it arises, you can treat numbers like [x/5] as being equal to x/5.]

      Well, they arose, the above simplifies to something like n*(1 + 1/2 + 1/3 + ... + 1/n) - n which is O(n log(n) )