Math 2320 -- Test 1A -- Whiteley -- October 9, 8:30

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

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

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

Therefore |f(n)| < (C*3) n^2 for all n> k
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.

(1 mark) State whether this is True or False?
If f(n) is O(n^2) then f(n) is bigger than 100 for some n.
If true, give an example, if false, give a counterexample.

This is false. (1/2 mark)
f(n)=1 is the kind of counter-example we'd expect.
This is both O(n^2) and f(n) < 100 for all n (1/2 mark)

(5 marks) In the following algorithm t is just used to count the number of critical steps.
Procedure closest pair ((a_1,a_2, ... ,a_n); n integers)
d:=0 ; {d is the distance between the first two points }
t:=1  { t will count the number of basic steps }
for i:=3 to n
begin
 j:= 1
t:=t+1  { t will count the number of basic steps }
 while  j < i 
begin
 e:=|a_i - a_j |
 t:= t+1 { t still counts the number of basic steps }
 Ife < d then d:=e
 { update d if we find a smaller value }
end
 end
 {d will be the smallest distance among pairs of points}

(a) (roughly 3 marks) What is the value of the counter t as a function of n ?
[A sum of terms is an acceptable answer for part (a).]

A goood method is to track increasing values of i
If i=2 , then we have t= 1 and no while loops.
If i=3 , then the while loops exactly 2 times, adding 2(2) to t ..
If i=4 , then the while loops exactly 3 times, adding 2(3) to t ..
In general, for a fixed value of i, the while loop, runs (i-1) times, adding 2(i-1) to t .

Therefore we get the expression: 1 + 2(2) + 2(3) + ... + 2(n-1)

[We can add up these to get -1 +2(n-1)(n)/2 = n(n-1) -1 , but this is not necessary.]

(b) (roughly 2 marks - if done correctly, even from a 'wrong' answer for (a) )
What is the time complexity, as calculated by t, in the worst case?

All cases are the 'worst case'. The above sum can be replaces by the larger sum:
1 + 2(2) + 2(3) + ... + 2(n-1) < n+n+ ... +n = n^2 for > 1

This is O(n^2 )