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) )