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:
“There is a certain standard of grace and beauty which consists in a certain relation between our nature, such as it is, weak or strong, and the thing which pleases us. Whatever is formed according to this standard pleases us, be it house, song, discourse, verse, prose, woman, birds, rivers, trees, room, dress, and so on. Whatever is not made according to this standard displeases those who have good taste.”
—Blaise Pascal (1623–1662)
“Parents ought, through their own behavior and the values by which they live, to provide direction for their children. But they need to rid themselves of the idea that there are surefire methods which, when well applied, will produce certain predictable results. Whatever we do with and for our children ought to flow from our understanding of and our feelings for the particular situation and the relation we wish to exist between us and our child.”
—Bruno Bettelheim (20th century)
“If a man has been his mother’s undisputed darling he retains throughout life the triumphant feeling, the confidence in success, which not seldom brings actual success along with it.”
—Sigmund Freud (1856–1939)
“Life is difficult for those who have the daring to first set out on an unknown road. The avant-garde always has a bad time of it.”
—Anton Pavlovich Chekhov (1860–1904)