Introduction
In many recent books, the goddamn endnotes are numbered sequentially within each chapter, but chapter numbers seldom appear in the header on each page. So a reader who wants to find a goddamn endnote typically has to search backward to figure out which chapter they are reading before they can find the goddamn endnote. Several simple changes can make this process more efficient and less infuriating.
In this paper, we present a novel algorithm for finding a goddamn endnote (FGE) in O(1) time; that is, time bounded by a constant regardless of the size or number of chapters.
Background
The most widely deployed algorithm for FGE requires O(n+m) time; that is, time proportional to either n, the number of pages in a chapter, or m, the number of chapters, whichever is larger. The following pseudocode sketches this algorithm:
1) Store the endnote number you want to find as e.
2) Figure out what chapter you are reading by searching for the beginning of the chapter, and store the result as c.
3) Find the footnotes at the end of the chapter and find the footnotes for chapter c.
4) Look up footnote e.
The most common implementation of Step 2 is linear in n, the number of pages in the chapter. Some readers can execute a binary search by comparing chapter titles in the header, reducing search time to O(log n).
Similarly, the most common implementation of Step 3 is linear in m, the number of chapters, but some readers perform a binary search.
Assuming that the number of footnotes in a chapter is bounded by a constant, we consider Step 4 to be constant time.
Alternatives
1) Put the goddamn chapter number (GCN) in the goddamn header. This simple change immediately reduces Step 2 to constant time.
2) Number the goddamn endnotes from the beginning to the end of the book. Do not start over at the beginning of each goddamn chapter. This change also reduces Step 2 to constant time, but with this change Step 4 may no longer be considered constant time.
3) Along with the endnote number, e, also include p, the page where the goddamn endnote appears. This change makes Step 2 constant time; and Step 3, although technically log time, practically constant time for most readers.
4) Put the goddamn endnotes at the bottom of the goddamn page (cf. footnotes). For a bounded page size, looking at the bottom of the page is a constant time operation.
Recommendations
We recommend that publishers replace existing linear-time algorithms with any of several easy-to-implement, efficient alternatives, goddammit.