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:
“Any relation to the land, the habit of tilling it, or mining it, or even hunting on it, generates the feeling of patriotism. He who keeps shop on it, or he who merely uses it as a support to his desk and ledger, or to his manufactory, values it less.”
—Ralph Waldo Emerson (1803–1882)
“The persons who constitute the natural aristocracy, are not found in the actual aristocracy, or, only on its edge; as the chemical energy of the spectrum is found to be greatest just outside of the spectrum.”
—Ralph Waldo Emerson (1803–1882)
“When peaceful clouds were reflected in the paddies
and the water buffalo stepped surely along terraces,
maybe fathers told their sons old tales.
When bombs smashed those mirrors
there was time only to scream.”
—Denise Levertov (b. 1923)