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 between, relation, actual and/or time:
“You know there are no secrets in America. It’s quite different in England, where people think of a secret as a shared relation between two people.”
—W.H. (Wystan Hugh)
“Hesitation increases in relation to risk in equal proportion to age.”
—Ernest Hemingway (1899–1961)
“Museums, museums, museums, object-lessons rigged out to illustrate the unsound theories of archaeologists, crazy attempts to co-ordinate and get into a fixed order that which has no fixed order and will not be co-ordinated! It is sickening! Why must all experience be systematized?... A museum is not a first-hand contact: it is an illustrated lecture. And what one wants is the actual vital touch.”
—D.H. (David Herbert)
“There was no speculation so promising, or at the same time so praisworthy, as the United Metropolitan Improved Hot Muffin and Crumpet Baking and Punctual Delivery Company.”
—Charles Dickens (1812–1870)