186
Recursion, Recurrence Relations, and Analysis of Algorithms
T(n) = (1)
n−1
(2) + ∙
n
i=2
(1)
n−i
(i + 1)
= 2 + ∙
n
i=2
(i + 1)
= 2 + (3 + 4 + c + (n + 1))
=
(n + 1)(n + 2)
2
− 1
(from Practice 7, Section 2.2)
example 19
Consider the problem of reading data from a computer disk drive.
4
The circular
drive is organized as a series of concentric tracks, divided into sectors. Each sector
contains a block of data (Figure 3.1).
The time to read a particular block of data into memory has three components:
1. Seek time—the time to position the read head over the proper track. This
time varies depending on the relative position of the read head and the
proper track when the read request is generated. In the best case, the read
head is already over the proper track and the seek time is 0. At the worst
case, assuming there are n tracks, the read head might be over track 1 and
have to move to track n, which would be n − 1 units, where a unit is the
distance between adjacent tracks. We can assume that the seek time would
be some multiple of the number of units.
2. Latency time—the time for the proper sector to rotate underneath the read
head. This time also varies, depending on whether the correct sector is just
coming under the read head (minimum latency time) or whether it has just
gone by and a full rotation must occur (maximum latency time).
3. Transfer time—the time to read a block once it is positioned under the read
head, usually a constant amount of time for all blocks.
The problem is to find the average seek time, actually the average number A(n) of
units. The assumptions are that there are n tracks, the read head is positioned over
some track i, and the read head is equally likely to have to move to any track j.
Figure 3.1
4 This example is based on work found in “Research Problem for Undergraduate Students which Spans
Hardware Issues, Mathematical Methods and Programming: Average Seek Time of a Computer Disk,” by
Jan Plaza, http://faculty.plattsburgh.edu/jan.plaza/teaching/papers/seektime.html
Recursion, Recurrence Relations, and Analysis of Algorithms
T(n) = (1)
n−1
(2) + ∙
n
i=2
(1)
n−i
(i + 1)
= 2 + ∙
n
i=2
(i + 1)
= 2 + (3 + 4 + c + (n + 1))
=
(n + 1)(n + 2)
2
− 1
(from Practice 7, Section 2.2)
example 19
Consider the problem of reading data from a computer disk drive.
4
The circular
drive is organized as a series of concentric tracks, divided into sectors. Each sector
contains a block of data (Figure 3.1).
The time to read a particular block of data into memory has three components:
1. Seek time—the time to position the read head over the proper track. This
time varies depending on the relative position of the read head and the
proper track when the read request is generated. In the best case, the read
head is already over the proper track and the seek time is 0. At the worst
case, assuming there are n tracks, the read head might be over track 1 and
have to move to track n, which would be n − 1 units, where a unit is the
distance between adjacent tracks. We can assume that the seek time would
be some multiple of the number of units.
2. Latency time—the time for the proper sector to rotate underneath the read
head. This time also varies, depending on whether the correct sector is just
coming under the read head (minimum latency time) or whether it has just
gone by and a full rotation must occur (maximum latency time).
3. Transfer time—the time to read a block once it is positioned under the read
head, usually a constant amount of time for all blocks.
The problem is to find the average seek time, actually the average number A(n) of
units. The assumptions are that there are n tracks, the read head is positioned over
some track i, and the read head is equally likely to have to move to any track j.
Figure 3.1
4 This example is based on work found in “Research Problem for Undergraduate Students which Spans
Hardware Issues, Mathematical Methods and Programming: Average Seek Time of a Computer Disk,” by
Jan Plaza, http://faculty.plattsburgh.edu/jan.plaza/teaching/papers/seektime.html