Section 3.2 Recurrence Relations
187
Table 3.3 shows the number of units in going from one track to another, where
a row is the source track and a column is the destination track. For example, if the
read head is currently over track 3 and must end up over track n, then n − 3 units are
required, as shown by the entry in row 3, column n. The entry in row n, column 3 is
the same because it takes the same number of units to move in the opposite direction.
table 3.3
1
2
3
c
n − 1
n
1
0
1
2
c
n − 2
n − 1
2
1
0
1
c
n − 3
n − 2
3
2
1
0
c
n − 4
n − 3
c
c
c
c
n − 1
n − 2
n − 3
n − 4
c
0
1
n
n − 1
n − 2
n − 3
c
1
0
Destination
track
Source
track
Table 3.3 illustrates the n
2
different possible track moves. We find the average
number A(n) of units for these n
2
cases by computing the total number of units
shown in the table, T(n), and then dividing by n
2
. To compute T(n), note that
T(n) = T(n − 1) + (the total of the last row plus the last column) and that the last
row plus the last column contribute
2[1 + 2 + 3 + c + (n − 1)] = 2 c
(n − 1)n
2
d
(using Practice 7, Section 2.2)
= (n − 1)n
so that
T(n) = T(n − 1) + (n − 1)n
The base case is T(1) = 0 (no seek time for a 1-track disk). This is a linear,
first-order recurrence relation with constant coefficients. We can solve it using
Equation (8), where c = 1 and g(n) = (n − 1)n. The solution is
T(n) = 0 + ∙
n
i=2
(i − 1)i
= 1 # 2 + 2 # 3 + 3 # 4 + c + (n − 1)n
=
(n − 1)n(n + 1)
3
(from Exercise 19, Section 2.2)
Therefore the average number of units is
A(n) =
(n − 1)n(n + 1)
3
/ n
2
=
n
3
− n
2
+ n
2
− n
3n
2
=
n
3
− n
3n
2
=
n
2
− 1
3n
=
n
3
−
1
3n
Because the best case is 0 and the worst case is n − 1, we might have expected the
average case to be close to n/2, but in fact it is slightly less than n/3.