Online Algorithms

Why this model exists

In many real systems, you don’t get the whole input upfront.

• •A cache sees a stream of memory requests.
• •A router sees packets arrive over time.
• •A ride-sharing platform sees trip requests in real time.
• •A cloud service sees jobs arrive continuously.

If you had the full future sequence, you could compute a globally optimal plan. But in reality, decisions must be made as the sequence unfolds.

Online algorithms capture this: input arrives piecewise, and the algorithm must decide using only information revealed so far.

The online decision model (informal → formal)

Think of time steps $t = 1, 2, \dots$.

• •At step $t$, an item $\sigma_t$ arrives (a request, job, price, etc.).
• •The algorithm outputs an action $a_t$.
• •Actions can change state (e.g., what’s in cache) and incur cost (e.g., a cache miss).
• •Crucially: no peeking at $\sigma_{t+1}, \sigma_{t+2}, \dots$.

Formally, an online algorithm is a rule that maps the prefix $\sigma_{1:t}$ to an action:

Often, the action is irrevocable (or at least has irreversible consequences). For example, if you evict a page from cache, you can’t magically have kept it.

The offline benchmark: OPT

To judge an online algorithm, we need a gold standard.

• •OPT is the optimal offline algorithm (also called the clairvoyant algorithm).
• •OPT knows the entire input sequence $\sigma_{1:T}$ in advance.
• •OPT returns the minimum possible cost (or maximum value).

We’ll write:

• •$\mathrm{ALG}(\sigma)$ = cost incurred by an online algorithm on sequence $\sigma$.
• •$\mathrm{OPT}(\sigma)$ = cost incurred by the optimal offline algorithm on the same sequence.

Why competitive analysis (instead of probability)

Sometimes you can assume a distribution (average-case). Competitive analysis is different: it’s worst-case, and it doesn’t require any distribution.

The mindset:

• •The future could be adversarial.
• •Your guarantee should hold on every sequence.

This is a powerful lens for systems where “rare bad cases” are unacceptable.

An interactive visualization to build intuition (timeline + prefix view)

On an interactive canvas, represent the request sequence as a timeline.

Visualization idea: Prefix timeline (core mental model)

• •Draw a horizontal timeline with ticks for $t=1..T$.
• •At time $t$, only the prefix $\sigma_{1:t}$ is visible (bright). The suffix $\sigma_{t+1:T}$ is hidden (greyed out).
• •When you click “Next”, one more request is revealed.

Side-by-side panels

• •Left: Online algorithm state (what it currently holds/decides).
• •Right: OPT state (shown only for comparison; it “magically” knows the future).

This is not just decoration: it concretizes the asymmetry—ALG must commit with partial info while OPT is clairvoyant.

Competitive ratio (definition)

There are two common cases:

1) Cost minimization (paging, ski rental, scheduling with penalties):

An online algorithm is $c$-competitive if there exists a constant $\alpha$ such that for all sequences $\sigma$,

2) Value maximization (online matching, ad allocation):

An online algorithm is $c$-competitive if for all sequences $\sigma$,

In this lesson we’ll mostly use cost minimization.

Interpreting the constants

• •The multiplicative factor $c$ is the main headline.
• •The additive constant $\alpha$ often handles “startup effects” (e.g., initial cache warm-up).
• •For long sequences, $\alpha$ becomes negligible compared to the total cost.

A small but important subtlety: adversaries

Competitive analysis can be stated against different adversary models:

When we discuss randomized algorithms later, we’ll implicitly assume an oblivious adversary unless stated otherwise.

Why proofs look different online

In offline algorithm analysis, you often prove optimality or approximation via structural arguments (“greedy stays ahead”).

In online algorithms, you frequently prove inequalities of the form:

Because OPT knows the future, you cannot directly compare step-by-step decisions. Instead, you compare costs using one of these strategies:

1) Charging arguments: charge each online cost to something OPT must also pay.

2) Partition into phases: group the sequence into chunks where OPT must pay at least 1 per chunk.

3) Potential functions: define a “stored credit” $\Phi$ so that

Summing over time telescopes the potential.

We’ll use all three.

Canonical Example: Ski Rental

The problem

You want to ski for an unknown number of days $D$.

• •Renting costs $1$ per day.
• •Buying costs $B$ once.
• •If you buy, you pay $B$ and then ski for free thereafter.

You must decide each day whether to rent again or buy now, without knowing $D$.

Offline OPT

If OPT knows $D$:

• •If $D < B$, rent every day → cost $D$.
• •If $D \ge B$, buy on day 1 → cost $B$.

So:

A deterministic online algorithm: “Rent until day B, then buy”

Define ALG:

• •Rent for the first $B-1$ days.
• •If still skiing on day $B$, buy at the start of day $B$.

ALG cost:

• •If $D < B$: ALG rents $D$ days → $\mathrm{ALG}(D)=D$.
• •If $D \ge B$: ALG rents $B-1$ days and buys once → $\mathrm{ALG}(D)= (B-1) + B = 2B-1$.

Competitive ratio proof (clean case split)

We want $\mathrm{ALG}(D) \le c\,\mathrm{OPT}(D) + \alpha$.

Case 1: $D < B$

So ratio is 1.

Case 2: $D \ge B$

and

Thus

So the algorithm is 2-competitive (and in fact $2 - 1/B$-competitive with tighter arithmetic).

Why 2 is essentially the best possible deterministically

There is a standard lower bound: no deterministic online algorithm can have competitive ratio < 2 for ski rental.

Intuition:

• •If you buy too early, adversary stops immediately → you overpaid.
• •If you buy too late, adversary keeps going → you should have bought.

A deterministic strategy has a fixed “buy day” $k$. The adversary chooses:

• •$D=k-1$ (punish early buying), or
• •$D=k$ or larger (punish late buying)

to force ratio approaching 2.

Interactive visualization: step-through Ski Rental (ALG vs OPT)

Canvas layout

• •Timeline days 1..T.
• •Buttons: “Reveal next day”, “Stop season now”.
• •Two rows:
• •ALG row: shows “rent” or “buy” decisions with cumulative cost.
• •OPT row: shows OPT’s best action given full D.

Key interaction

• •Let the learner play adversary: choose when the season ends.
• •Show the ratio $\mathrm{ALG}(D)/\mathrm{OPT}(D)$ live.
• •Let learner slide the buy threshold $k$ and see worst-case ratio change.

This makes the adversarial nature of competitive analysis tangible.

Competitive analysis checklist (how to structure proofs)

When you face a new online problem, ask:

1) What is the state? What decisions are irreversible?

2) What does OPT do with full knowledge?

3) What is a natural online heuristic? (Often greedy.)

4) How can you lower-bound OPT’s cost on any sequence?

5) How can you upper-bound ALG’s cost and connect it to that lower bound?

This becomes especially important in paging, where the proof technique is more “global”.

The paging (caching) problem

You have a cache that holds $k$ pages.

• •Requests arrive as a sequence $\sigma_1, \sigma_2, \dots, \sigma_T$.
• •If the requested page is in cache: cost 0 (a hit).
• •Otherwise: cost 1 (a miss), and you must bring it in.
• •If cache is full, you must evict some page.

Goal: minimize total misses.

This is a quintessential online problem: you do not know future requests, so eviction is hard.

OPT for paging

OPT is the optimal offline caching algorithm. A famous optimal offline rule is Belady’s algorithm:

• •On a miss, evict the page whose next use is farthest in the future.

You cannot implement this online (it needs the future), but it defines OPT.

Deterministic algorithms: LRU and FIFO

Two classic online strategies:

• •LRU (Least Recently Used): evict the page that was used least recently.
• •FIFO: evict the page that has been in cache the longest.

Both are simple and widely used.

The theorem (high-level)

LRU and FIFO are $k$-competitive for paging with cache size $k$.

Meaning: for all sequences $\sigma$,

Usually $\alpha$ can be taken as $k$ or $k-1$.

We’ll focus on the proof idea and a potential-function visualization.

Phase partitioning: a lower bound on OPT

Why phases are useful

If we can partition the request sequence into chunks where:

• •ALG pays at most $k$ per chunk, and
• •OPT must pay at least 1 per chunk,

then ALG is $k$-competitive.

Define phases (for LRU/FIFO analysis)

A standard definition:

• •Start phase 1 at the first request.
• •Keep extending the phase until you have seen $k+1$ distinct pages in the current phase.
• •End the phase right before the request that would introduce the $(k+1)$-th distinct page.
• •Start a new phase at that request.

So each phase contains requests to at most $k$ distinct pages.

Key facts

1) ALG incurs ≤ k misses per phase (for LRU/FIFO).

• •Because each phase has at most $k$ distinct pages, after at most $k$ misses ALG can load them all.

2) OPT incurs ≥ 1 miss per phase boundary.

• •Consider two consecutive phases. Together they involve at least $k+1$ distinct pages (by construction).
• •OPT has cache size $k$ and cannot hold all $k+1$ pages across the boundary.
• •Therefore at least one request among those must be a miss for OPT.

Thus:

• •If there are $P$ phases, ALG has at most $kP$ misses.
• •OPT has at least $P-1$ misses (sometimes $P$ depending on convention).

So:

This yields $k$-competitiveness.

Interactive visualization: phase segmentation with live counters

Canvas elements

• •A scrolling request stream with distinct pages color-coded.
• •A vertical divider marking the current phase.
• •A counter: “distinct pages in phase: d (≤ k)”.

Step-through behavior

• •Each request updates the set of distinct pages in the current phase.
• •When a new page would make $d = k+1$, flash a “phase ends” event, start next phase.

Side-by-side miss counts

• •Track misses for LRU (or FIFO) and show “≤ k per phase” as a bar that fills up to k.
• •Track OPT lower bound as “≥ 1 per phase boundary” as a single token per boundary.

This makes the proof’s core comparison visual: k tokens vs 1 token per phase.

Potential functions: making amortized reasoning concrete

Phase arguments are powerful but sometimes too coarse. Potential functions let you prove more refined statements and are reusable.

The pattern

Define a potential $\Phi_t$ based on the algorithm’s state and OPT’s state at time $t$.

You aim to prove an inequality per step:

Then sum over $t=1..T$:

\begin{align}

\sum_t \text{ALG}_t + \sum_t (\Phi_t - \Phi_{t-1}) &\le c \sum_t \text{OPT}_t \\

\mathrm{ALG}(\sigma) + (\Phi_T - \Phi_0) &\le c\,\mathrm{OPT}(\sigma).

\end{align}

Because the potential telescopes, you get:

If $\Phi$ is always nonnegative, then $-\Phi_T \le 0$, so the additive term is at most $\Phi_0$.

A potential for paging (conceptual)

For LRU, one classic proof uses a potential related to “how many pages are in OPT’s cache but not in ALG’s cache,” but the full tight potential proof is intricate.

Instead, use potential to visualize telescoping on the canvas:

Visualization: Potential telescope meter

• •Define $\Phi_t = |\text{OPT cache} \setminus \text{ALG cache}|$ (size of set difference).
• •Show two cache boxes with page labels.
• •Show a third box labeled “Potential” containing the pages that are in OPT but not ALG.

When a miss happens:

• •ALG brings a page in (may reduce potential if it matches one OPT has).
• •OPT may also miss and change its cache (may increase or decrease potential).

Even if you don’t complete the full rigorous inequality for LRU in this lesson, the visualization teaches the method: potential stores “debt/credit” that can go up and down, and the proof is about bounding cost + Δpotential.

Why this matters for later nodes

Potential functions are the online-algorithms cousin of amortized analysis in data structures. The same “telescope” trick appears in splay trees, dynamic arrays, and primal-dual online methods.

Randomization preview (why it helps)

Deterministic paging has a lower bound: no deterministic online paging algorithm can beat competitive ratio $k$.

Randomization can do better:

• •There are randomized algorithms with competitive ratio $H_k = 1 + 1/2 + \dots + 1/k \approx \ln k$.

You don’t need to master these yet, but keep the principle:

• •Randomness prevents the adversary from always predicting your evictions.

If you later study the randomized paging algorithm (e.g., MARK), the phase concept returns, but the expectation is handled carefully.

Interactive visualization: paging simulator (LRU vs OPT vs Random)

Core canvas design

• •Three columns: LRU, FIFO (or Random), OPT.
• •Each column shows a cache of size $k$ with page slots.
• •A request stream runs down the center.

Step controls

• •Step forward/backward.
• •Toggle “show OPT’s next-use distances” (to illustrate Belady’s rule).

Metrics

• •Miss counters.
• •Live ratio estimate: $\mathrm{ALG}/\mathrm{OPT}$.
• •Phase counter and distinct-set display.

The goal: learners see that OPT’s evictions look “weird” locally but are globally optimal because OPT sees the future.

Why online algorithms matter in practice

Competitive analysis is a theory tool, but it maps to real engineering constraints:

• •Caching (CPU caches, CDN edge caches): paging is the core abstraction.
• •Resource provisioning (cloud autoscaling): you must allocate servers without knowing future demand.
• •Networking (packet scheduling, congestion control): decisions are made on streaming inputs.
• •Auctions and ads (online allocation): allocate impressions as users arrive.
• •Robotics (navigation with unknown terrain): decisions without full map.

How to choose an online metric

Competitive ratio is worst-case; it can be pessimistic. But it is useful when:

• •You need hard guarantees.
• •Inputs can be adversarial.
• •You want robustness.

In more benign environments, you may combine competitive analysis with:

• •Stochastic assumptions (prophet inequalities, regret bounds).
• •Smoothed analysis.

A unifying mental model: ALG vs OPT as two “players”

Many proofs become clearer if you imagine:

• •OPT is a player that knows the entire script.
• •ALG is improvising.
• •The analysis is about showing OPT cannot outperform ALG by more than a factor $c$.

Common proof tools you now have

• •Lower-bounding OPT via information constraints (cache size, irrevocability).
• •Partitioning into phases to extract “OPT must pay at least 1 here”.
• •Potential functions to amortize costs and telescope sums.

Suggested canvas interactions (explicit conceptual work)

If you are implementing this node in an interactive tech tree UI, these interactions do real teaching work:

1) Ski rental adversary game

• •Learner chooses the season end day $D$ after seeing ALG’s policy.
• •UI displays worst-case ratio over all $D$ for a chosen threshold $k$.

2) Paging step-through with phase highlights

• •Each new distinct page increments a “distinct-in-phase” counter.
• •When it hits $k+1$, the UI visually splits phases and drops a token in OPT’s “must miss” bucket.

3) Potential telescope meter

• •Show $\Phi_t$ over time as a bar plot.
• •Show that the proof sums “ALG cost + ΔΦ” and ΔΦ cancels across steps.

These visualizations are not optional decoration—they mirror the structure of the analysis.