This is a semi-open-ended question; there could be several right answers depending on how the analysis is carried out. The crucial observation to make, however, is that it takes O(Wt) time to find words on a page; that is, the search has to touch every word.
Because any word can appear on any page, it seems reasonable to conclude that a search for pages containing a particular word would also have to touch every word, and so also take O(Wt) time. You could assume the words are stored in order, but that doesn't change the worst-case behavior (it does change the average-case behavior).
If the words are ordered, you could also assume an auxiliary array containing pointers into the word list. The auxiliary array reduces word finding to O(log Wt) (this assumes first letters follow a uniform distribution, which is wrong but reasonable for this question).
Most answers to this question went astray by apparently confusing page searching with word searching. A few answers failed to recognize that if there were p pages and Wp words per page on average, then pWp is approximately Wt.
See Section 6.6 in Nyhoff.
Way too many answers to this question were wrong, some of them forgetting about the constant-time add requirement.
It does not: where would you put the extra elements allocated?
Way too many answers to this question were wrong. Even the right answers were too long.
A dequeue has element access restricted to the ends; a linked list has no such restriction.
Way too many answers to this question were wrong, either by not knowing what a dequeue was, or by not knowing what a linked list was.
This page last modified on 3 March 2006.