Advanced Algorithmic Analysis

In standard algorithm analysis, we often focus on the worst-case complexity of a single operation.
However, this can be overly pessimistic for data structures where a single expensive operation is
necessarily preceded by many inexpensive ones. This module explores techniques to provide tighter,
more realistic bounds on performance through probabilistic inequalities, amortized analysis, and
competitive analysis.

1. Probabilistic Inequalities in Analysis

When analyzing randomized algorithms, we often deal with random variables representing running
time or resource usage. Probabilistic inequalities allow us to bound the probability that these variables
deviate significantly from their expected value.

1.1 Markov’s Inequality This is the most fundamental tail bound. It applies to any non-negative random
variable X . It provides a loose upper bound on the probability that X is much larger than its expectation
E [X ].

E[ X ]
P( X ≥ a)≤ for any a>0
a
 Intuition: If the average height of a group is 1.7 m , at most 50 % of the group can be 3.4 m or
taller.

 Limitation: It is a “weak” bound because it only uses the mean and does not consider how
spread out the data is.
2
1.2 Chebyshev’s Inequality If we know the variance V a r ( X)=σ , we can get a much tighter bound. It

limits how much X can deviate from its mean μ in either direction.
1
P(¿ X − μ∨≥ k σ )≤ 2
k
 Application: Useful when the variance is small. It guarantees that most of the probability mass is
concentrated near the mean.
1.3 Chernoff Bounds For a sum of independent Bernoulli trials (like coin flips), Chernoff bounds provide
exponentially decreasing tail probabilities. This is the “gold standard” for proving that a randomized
algorithm succeeds with high probability.

P( X ≥(1+ δ)μ)≤¿ ¿
2. Amortized Analysis: The Core Concept
Amortized analysis is used when a sequence of operations is performed. Instead of looking at the
worst-case cost of one operation, we look at the average cost per operation over the entire sequence.

Crucial Distinction: Unlike average-case analysis, amortized analysis does not involve probability. it is a
guaranteed bound on the total cost of a sequence of operations in the worst case.

2.1 The Aggregate Method

This is the simplest form. We calculate the total cost T (n) for a sequence of n operations and then

compute the amortized cost as T (n)/n.

Example: The Dynamic Array (Vector) Consider an array that doubles in size when full.

 Push cost: Usually 1 (inserting the element).

 Resize cost: When the array of size k is full, we allocate a new array of size 2 k and copy k
elements. Cost = k +1 .

Analysis: In a sequence of n insertions, resizes happen at n=1 ,2 , 4 ,8 , … , 2i . The total cost T (n) is:

log2 n
T (n)=n+ ∑ 2
i

i=0

k k+1
Using the geometric series formula ∑ r i= r r −−1
1
:
i=0

T (n)=n+(2 n −1)< 3 n
 3n
The amortized cost per operation is =O(1).
n

2.2 The Accounting Method (The Banker’s Method)

In this method, we assign different charges to different operations. We “overcharge” cheap operations
and save the extra as credit. This credit is later used to pay for expensive operations.

Rules:

1. Let c i be the actual cost of operation i .

2. Let c^ i be the amortized cost (the amount we charge).

3. The total credit stored must always be non-negative: ∑ c^ i ≥∑ ci .

Example: Dynamic Array (Accounting)

 Actual cost of Push: 1 (if no resize) or k +1 (if resize from k to 2 k ).

 Amortized charge: Set c^ i=3 .

 Logic:

 1 unit pays for the current insertion.

 1 unit is stored to pay for moving this element later during a resize.
 1 unit is stored to pay for moving another element that was already in the array but has no credit
left.

 When the array doubles from size k to 2 k , we have exactly k units of credit stored, which
perfectly pays for the k copies needed.

2.3 The Potential Method (The Physicist’s Method)

Instead of credit on individual items, we define a potential function Φ that represents the “energy” or
“stored work” of the entire data structure.

Let Di be the state of the data structure after operation i. The amortized cost c^ i is:

c^ i=ci +Φ (Di )−Φ (Di −1 )

The total amortized cost for n operations is:

n n

∑ c^ i =∑ c i +Φ(D n)−Φ ( D0 )
i=1 i=1

Example: Binary Counter Consider a binary counter where the cost c i is the number of bits flipped

during an increment.

 Potential Function: Φ ( D i)=number of 1s in the counter .

 Increment Operation: Suppose it flips k bits to 0 and then one bit to 1.

 Actual cost c i=k +1.

 Change in potential Δ Φ=Φ (Di )− Φ(Di − 1)=1 − k (one bit became 1, k bits became 0 ).
  Amortized cost c^ i=(k +1)+(1 − k)=2.

 Thus, the amortized cost of an increment is O(1).

3. Competitive Analysis
Competitive analysis is used for online algorithms, which must make decisions without knowing the
future (e.g., a cache deciding which page to evict).

We compare the performance of our online algorithm A against an Optimal Offline Algorithm (O P T )
that knows the entire sequence of requests in advance.

Competitive Ratio: An algorithm A is c -competitive if for all sequences I :

C o s t A (I )≤ c ⋅C o s t O P T (I )+b

where b is a constant.

3.1 The Ski Rental Problem

You are going skiing. You don’t know how many days the season will last ( L).

 Rent: $ 10 per day.

 Buy: $ 100 once.
Strategy: Rent for 9 days. If you go on the 10 th day, buy the skis.

 Case 1: Season ends at day k < 10.

 Your cost: 10 k . O P T cost: 10 k . Ratio = 1.

 Case 2: Season ends at day k ≥ 10.

 Your cost: 90 (rent)+100 (buy )=190.

 OPT cost: 100 (would have bought on day 1).

  Ratio = 190/100=1.9.

 This algorithm is 1.9-competitive. In general, for buy cost B and rent cost R , the ratio is roughly
2 − R/ B.

3.2 Paging/Caching
When a memory page is requested and not in the cache, we must evict one.

 LRU (Least Recently Used): Evicts the page not used for the longest time.

 FIFO (First-In, First-Out): Evicts the oldest page.

 Theorem: Both LRU and FIFO are k -competitive, where k is the size of the cache. This is the best
possible ratio for any deterministic online paging algorithm.

4. Summary of Methods
Method Perspective Best Used For…

Aggregate Global Simple structures where total

cost is easy to sum.

Accounting Local (Items) When costs can be associated

with specific elements.

Potential Global (State) Complex structures where state

change is easier to track.

Competitive Online vs Offline Scenarios with uncertainty about

future inputs.

Common Pitfall: In the Potential Method, if Φ ( D n)<Φ (D 0 ), the amortized cost might underestimate

the actual cost. Always ensure Φ ( D i)≥ Φ(D 0) for all i to guarantee that the amortized bound is a true

upper bound on the actual total cost.