Complexity Analysis

Question 1

Accumulation technique

Answer 1

Show that n actions cost T(n) so therefore a single action costs T(n)/n

Question 2

Charging technique

Answer 2

Ramp up the “price” of using “cheap” operations, that way the “price” of the expensive ones cancel out with the cheaper ones.

Question 3

The potential method

Answer 3

Create a function that reflects the potential that the data structure has.
The function for a single action wil be:
C = actual_cost + P(Di) - P(Di-1)
P(Dn) >= P(0)

Question 4

Proving correctness of Potential function

Answer 4

To prove the correctness of a potential function:
1. Prove that the value is non negative.
2. Prove that the complexity is as wanted.

Question 5

Dynamic list (idea)

Answer 5

We have a list but we don’t know how many items it will have. Solution: double the list’s size every time it is full.

Question 6

Dynamic list analysis

Answer 6

Takes O(1) for all actions. Using the charging method, each action costs 3 to pay for all of the items behind it.