Relation Between Amortized and Actual Time
Despite its artificial appearance, the total amortized time of a sequence of operations provides a valid upper bound on the actual time for the same sequence of operations. That is, for any sequence of operations, the total amortized time is always at least as large as the total actual time . In more detail,
where the sequence of potential function values forms a telescoping series in which all terms other than the initial and final potential function values cancel in pairs, and where the final inequality arises from the assumptions that and . Therefore, amortized time can be used to provide accurate predictions about the actual time of sequences of operations, even though the amortized time for an individual operation may vary widely from its actual time.
Read more about this topic: Potential Method
Famous quotes containing the words relation, actual and/or time:
“The difference between objective and subjective extension is one of relation to a context solely.”
—William James (1842–1910)
“Fine art, that exists for itself alone, is art in a final state of impotence. If nobody, including the artist, acknowledges art as a means of knowing the world, then art is relegated to a kind of rumpus room of the mind and the irresponsibility of the artist and the irrelevance of art to actual living becomes part and parcel of the practice of art.”
—Angela Carter (1940–1992)
“Women had to deal with the men’s response when the women wanted more time “out” of the home; men now must deal with the women’s response as men want more time “in.””
—Kyle D. Pruett (20th century)