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:
“You see, I am alive, I am alive
I stand in good relation to the earth
I stand in good relation to the gods
I stand in good relation to all that is beautiful
I stand in good relation to the daughter of Tsen-tainte
You see, I am alive, I am alive”
—N. Scott Momaday (b. 1934)
“You may well ask how I expect to assert my privacy by resorting to the outrageous publicity of being one’s actual self on paper. There’s a possibility of it working if one chooses the terms, to wit: outshouting image-gimmick America through a quietly desperate search for self.”
—Kate Millett (b. 1934)
“For five years I have seen her each day, and each time I believe it is for the first time.”
—Jean Racine (1639–1699)