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