Storing Files on Tape

Introduction to storing files

Suppose we have a set of $n$ files that we want to store on a magnetic tape. In the future, users will want to read those files from the tape. Reading a file from tape isn’t like reading a file from a disk; first, we have to fast-forward past all the other files, and that takes a significant amount of time. Let $L[1 .. n]$ be an array listing the lengths of each file; specifically, file $i$ has length $L[i]$. If the files are stored in order from $1$ to $n$, then the cost of accessing the $k$th file is:

$$cost(k) = \underset{i=1}{\overset{k}\sum}L[i]$$

Expected cost of accessing a random file

The cost reflects the fact that before we read file $k$, we must first scan past all the earlier files on the tape. If we assume for the moment that each file is equally likely to be accessed, then the expected cost of searching for a random file is:

$$E[cost] = \underset{k=1}{\overset{n}{\sum}}\frac{cost(k)}{n} = \frac{1}{n} \underset{k=1}{\overset{n}{\sum}} \space \underset{i=1}{\overset{k}{\sum}}L[i]$$ ...