Amortized Analysis - Method

Method

The method requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have state that persists between operations. The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.

There are generally three methods for performing amortized analysis: the aggregate method, the accounting method, and the potential method. All of these give the same answers, and their usage difference is primarily circumstantial and due to individual preference.

  • Aggregate analysis determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the amortized cost to be T(n) / n.
  • The accounting method determines the individual cost of each operation, combining its immediate execution time and its influence on the running time of future operations. Usually, many short-running operations accumulate a "debt" of unfavorable state in small increments, while rare long-running operations decrease it drastically.
  • The potential method is like the accounting method, but overcharges operations early to compensate for undercharges later.

Read more about this topic:  Amortized Analysis

Famous quotes containing the word method:

    “Government by average opinion is merely a circuitous method of going to the devil; those who profess to lead but in fact slavishly follow this average opinion are simply the fastest runners and the loudest squeakers of the herd which is rushing blindly down to its destruction.”
    —Thomas Henry Huxley (1825–95)

    ““I have usually found that there was method in his madness.”
    “Some folk might say there was madness in his method.””
    —Sir Arthur Conan Doyle (1859–1930)

    “In child rearing it would unquestionably be easier if a child were to do something because we say so. The authoritarian method does expedite things, but it does not produce independent functioning. If a child has not mastered the underlying principles of human interactions and merely conforms out of coercion or conditioning, he has no tools to use, no resources to apply in the next situation that confronts him.”
    —Elaine Heffner (20th century)