Online Algorithms

←Back to Tech Tree

inventorycoverage

Online Algorithms #

AlgorithmsDifficulty: ★★★★☆Depth: 4Unlocks: 0

Decision-making without future information. Competitive analysis.

Interactive Visualization #

⏮◀◀▶▶STEP0.25x1xZOOM

t=0s

Core Concepts #

Key Symbols & Notation #

OPT (cost/value of the optimal offline solution)

Essential Relationships #

Prerequisites (2) #

Big O Notation6 atomsGreedy Algorithms6 atoms

Referenced by (1) #

Where this concept shows up in the operating-finance and personal-finance graphs.

From Business (1) #

[rent-vs-buy decisionBusiness

Ski rental IS the canonical online algorithms problem. Deterministic competitive ratio 2-1/B, randomized e/(e-1). Decision-making without knowing the future duration, analyzed via competitive analysis.](/business/rent-vs-buy-decision/)

Advanced Learning Details

Graph Position #

50

Depth Cost

0

Fan-Out (ROI)

0

Bottleneck Score

4

Chain Length

Cognitive Load #

6

Atomic Elements

32

Total Elements

L1

Percentile Level

L4

Atomic Level

All Concepts (15) #

Teaching Strategy #

Multi-session curriculum - substantial prior knowledge and complex material. Use mastery gates and deliberate practice.

Some algorithm problems feel “unfair”: you must act now, but the input will only be revealed later. Online algorithms are the formal way to reason about decision-making under uncertainty—where the adversary controls the future and your choices are (usually) irreversible.

TL;DR:

An online algorithm makes decisions using only the past and present, while OPT is a clairvoyant offline algorithm that knows the whole future. We evaluate online algorithms via competitive analysis: compare ALG to OPT on every input sequence and bound the worst-case ratio (or additive gap). Canonical examples like Ski Rental and Paging show how to design and prove guarantees, often using clean inequality chains or potential functions to “telescope” costs over time.

What Is an Online Algorithm? #

Why this model exists #

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

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,…t = 1, 2, \dotst=1,2,….

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

at=A(σ1:t).a_t = A(\sigma_{1:t}).at​=A(σ1:t​).

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.

We’ll write:

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:

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)

Side-by-side panels

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σ,

ALG(σ)≤c OPT(σ)+α.\mathrm{ALG}(\sigma) \le c,\mathrm{OPT}(\sigma) + \alpha.ALG(σ)≤cOPT(σ)+α.

  1. Value maximization (online matching, ad allocation):

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

ALG(σ)≥1c OPT(σ)−α.\mathrm{ALG}(\sigma) \ge \frac{1}{c},\mathrm{OPT}(\sigma) - \alpha.ALG(σ)≥c1​OPT(σ)−α.

In this lesson we’ll mostly use cost minimization.

Interpreting the constants #

A small but important subtlety: adversaries #

Competitive analysis can be stated against different adversary models:

Adversary typeWhat it can doTypical use
ObliviousFixes the whole sequence in advanceStandard for randomized algorithms
AdaptiveChooses next request after seeing your past actionsStronger (harder)

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

Core Mechanic 1: Competitive Analysis (How to Prove a Guarantee) #

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:

ALG(σ)≤c OPT(σ)+α.\mathrm{ALG}(\sigma) \le c,\mathrm{OPT}(\sigma) + \alpha.ALG(σ)≤cOPT(σ)+α.

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

ΔΦ+(ALG step cost)≤c⋅(OPT step cost).\Delta\Phi + \text{(ALG step cost)} \le c \cdot \text{(OPT step cost)}.ΔΦ+(ALG step cost)≤c⋅(OPT step cost).

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 DDD.

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

Offline OPT #

If OPT knows DDD:

So:

OPT(D)=min⁡(D,B).\mathrm{OPT}(D) = \min(D, B).OPT(D)=min(D,B).

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

Define ALG:

ALG cost:

Competitive ratio proof (clean case split) #

We want ALG(D)≤c OPT(D)+α\mathrm{ALG}(D) \le c,\mathrm{OPT}(D) + \alphaALG(D)≤cOPT(D)+α.

Case 1: D<BD < BD<B

ALG(D)=D=OPT(D).\mathrm{ALG}(D)=D = \mathrm{OPT}(D).ALG(D)=D=OPT(D).

So ratio is 1.

Case 2: D≥BD \ge BD≥B

OPT(D)=B,\mathrm{OPT}(D)=B,OPT(D)=B,

and

ALG(D)=2B−1≤2B.\mathrm{ALG}(D)=2B-1 \le 2B.ALG(D)=2B−1≤2B.

Thus

ALG(D)≤2 OPT(D).\mathrm{ALG}(D) \le 2,\mathrm{OPT}(D).ALG(D)≤2OPT(D).

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:

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

to force ratio approaching 2.

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

Canvas layout

Key interaction

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”.

Core Mechanic 2: Paging, Phases, and Potential Functions (Amortized Competitive Proofs) #

The paging (caching) problem #

You have a cache that holds kkk pages.

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:

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

Deterministic algorithms: LRU and FIFO #

Two classic online strategies:

Both are simple and widely used.

The theorem (high-level) #

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

Meaning: for all sequences σ\sigmaσ,

ALG(σ)≤k OPT(σ)+α.\mathrm{ALG}(\sigma) \le k,\mathrm{OPT}(\sigma) + \alpha.ALG(σ)≤kOPT(σ)+α.

Usually α\alphaα can be taken as kkk or k−1k-1k−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:

then ALG is kkk-competitive.

Define phases (for LRU/FIFO analysis) #

A standard definition:

So each phase contains requests to at most kkk distinct pages.

Key facts #

  1. ALG incurs ≤ k misses per phase (for LRU/FIFO).
  1. OPT incurs ≥ 1 miss per phase boundary.

Thus:

So:

ALG(σ)≤k OPT(σ)+k.\mathrm{ALG}(\sigma) \le k,\mathrm{OPT}(\sigma) + k.ALG(σ)≤kOPT(σ)+k.

This yields $k$-competitiveness.

Interactive visualization: phase segmentation with live counters #

Canvas elements

Step-through behavior

Side-by-side miss counts

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 Φt\Phi_tΦt​ based on the algorithm’s state and OPT’s state at time ttt.

You aim to prove an inequality per step:

(ALG cost at t)+(Φt−Φt−1)≤c⋅(OPT cost at t).\text{(ALG cost at t)} + (\Phi_t - \Phi_{t-1}) \le c \cdot \text{(OPT cost at t)}.(ALG cost at t)+(Φt​−Φt−1​)≤c⋅(OPT cost at t).

Then sum over t=1..Tt=1..Tt=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:

ALG(σ)≤c OPT(σ)+Φ0−ΦT.\mathrm{ALG}(\sigma) \le c,\mathrm{OPT}(\sigma) + \Phi_0 - \Phi_T.ALG(σ)≤cOPT(σ)+Φ0​−ΦT​.

If Φ\PhiΦ is always nonnegative, then −ΦT≤0-\Phi_T \le 0−ΦT​≤0, so the additive term is at most Φ0\Phi_0Φ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

When a miss happens:

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 kkk.

Randomization can do better:

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

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

Step controls

Metrics

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

Applications and Connections: Where Online Algorithms Show Up #

Why online algorithms matter in practice #

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

How to choose an online metric #

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

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

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

Many proofs become clearer if you imagine:

Common proof tools you now have #

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
  1. Paging step-through with phase highlights
  1. Potential telescope meter

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

Worked Examples (3) #

Worked Example 1: Ski Rental — Prove 2-Competitiveness of a Threshold Strategy #

Rent costs 1/day, buy costs B. Consider the deterministic online algorithm ALG: rent for B−1 days, then if still skiing on day B, buy. Let D be the (unknown) number of skiing days.

  1. Compute OPT(D):

    OPT knows D.

    • •If D < B, OPT rents every day → cost D.
    • •If D ≥ B, OPT buys immediately → cost B.

    Therefore:

    OPT(D)=min⁡(D,B).\mathrm{OPT}(D) = \min(D,B).OPT(D)=min(D,B).

  2. Compute ALG(D) by cases:

    • •If D < B, ALG never reaches day B, so it rents D days:

    ALG(D)=D.\mathrm{ALG}(D)=D.ALG(D)=D.

    • •If D ≥ B, ALG rents for B−1 days and buys once at day B:

    ALG(D)=(B−1)+B=2B−1.\mathrm{ALG}(D)=(B-1)+B = 2B-1.ALG(D)=(B−1)+B=2B−1.

  3. Bound the ratio when D < B:

    Here OPT(D)=D, so

    ALG(D)=D=OPT(D)≤2 OPT(D).\mathrm{ALG}(D)=D = \mathrm{OPT}(D) \le 2,\mathrm{OPT}(D).ALG(D)=D=OPT(D)≤2OPT(D).

  4. Bound the ratio when D ≥ B:

    Here OPT(D)=B, and

    ALG(D)=2B−1≤2B=2 OPT(D).\mathrm{ALG}(D)=2B-1 \le 2B = 2,\mathrm{OPT}(D).ALG(D)=2B−1≤2B=2OPT(D).

  5. Conclude competitiveness:

    For all D,

    ALG(D)≤2 OPT(D).\mathrm{ALG}(D) \le 2,\mathrm{OPT}(D).ALG(D)≤2OPT(D).

    So ALG is 2-competitive (with additive constant α=0).

Insight: This proof works because OPT has only two meaningful behaviors (rent-all or buy-immediately). The online difficulty is exactly at the unknown threshold D≈B, where an adversary can force either regret (buy too early) or regret (buy too late).

Worked Example 2: Paging — Phase Argument for k-Competitiveness (LRU/FIFO style) #

Paging with cache size k. Requests form a sequence σ. Define phases so that each phase contains requests to at most k distinct pages, and the next request would introduce the (k+1)th distinct page, starting a new phase. Consider ALG = LRU or FIFO.

  1. Define the phase partition precisely:

    Start phase 1 at t=1.

    Maintain a set S of distinct pages seen in the current phase.

    When processing request σ_t:

    • •If σ_t ∉ S and |S| = k, then σ_t would be the (k+1)th distinct page.
    • •End the current phase at t−1 and start a new phase at t with S = {σ_t}.

    Thus each phase contains ≤ k distinct pages.

  2. Upper-bound ALG’s misses per phase:

    Within a single phase, there are at most k distinct pages.

    ALG can miss at most once per distinct page when it first appears in the phase.

    So misses in a phase ≤ k.

    (After a page is loaded, subsequent requests in the same phase can be hits unless it gets evicted; for LRU/FIFO under this phase definition, the standard argument shows it won’t evict a page needed again within the phase before all k distinct pages have been loaded.)

  3. Lower-bound OPT’s misses across phases:

    Consider two consecutive phases i and i+1.

    By construction, phase i has k distinct pages, and phase i+1 starts with a new page not in phase i’s distinct set (otherwise we wouldn’t start a new phase).

    Therefore, across the boundary there are at least k+1 distinct pages that are requested in the union of the two phases.

    OPT’s cache holds only k pages, so it cannot have all k+1 pages resident at the times they are needed.

    Hence OPT must incur at least 1 miss attributable to each phase boundary.

  4. Relate totals:

    Let P be the number of phases.

    • •ALG misses ≤ kP.
    • •OPT misses ≥ P−1.

    So:

    ALG(σ)≤kP≤k(OPT(σ)+1)=k OPT(σ)+k.\mathrm{ALG}(\sigma) \le kP \le k(\mathrm{OPT}(\sigma)+1) = k,\mathrm{OPT}(\sigma) + k.ALG(σ)≤kP≤k(OPT(σ)+1)=kOPT(σ)+k.

  5. Conclude k-competitiveness:

    ALG is k-competitive with additive constant α = k.

Insight: The phase partition turns a messy streaming process into a counting argument: ALG spends ≤ k “tokens” per phase, while OPT must spend ≥ 1 token per phase boundary. This is the backbone of many competitive proofs: invent a structure where OPT is forced to pay regularly.

Worked Example 3: Potential-Function Telescoping on a Toy Online Cost Process #

You want to understand the telescoping pattern used in online proofs. Suppose an online process has per-step cost a_t, and you define a potential Φ_t ≥ 0. You manage to prove for every step t:

at+(Φt−Φt−1)≤c ot,a_t + (\Phi_t - \Phi_{t-1}) \le c,o_t,at​+(Φt​−Φt−1​)≤cot​,

where o_t is OPT’s per-step cost.

  1. Write the per-step inequality:

    For each t,

    at+(Φt−Φt−1)≤c ot.a_t + (\Phi_t - \Phi_{t-1}) \le c,o_t.at​+(Φt​−Φt−1​)≤cot​.

  2. Sum over t = 1..T:

    ∑t=1Tat+∑t=1T(Φt−Φt−1)≤c∑t=1Tot.\sum_{t=1}^T a_t + \sum_{t=1}^T (\Phi_t - \Phi_{t-1}) \le c \sum_{t=1}^T o_t.t=1∑T​at​+t=1∑T​(Φt​−Φt−1​)≤ct=1∑T​ot​.

  3. Recognize the telescope:

    The second sum cancels internally:

    \begin{align}

    \sum_{t=1}^T (\Phi_t - \Phi_{t-1})

    &= (\Phi_1-\Phi_0) + (\Phi_2-\Phi_1) + \dots + (\Phi_T-\Phi_{T-1}) \

    &= \Phi_T - \Phi_0.

    \end{align}

  4. Rewrite in total-cost form:

    Let ALG = ∑ a_t and OPT = ∑ o_t. Then

    ALG+(ΦT−Φ0)≤c OPT.\mathrm{ALG} + (\Phi_T - \Phi_0) \le c,\mathrm{OPT}.ALG+(ΦT​−Φ0​)≤cOPT.

  5. Use nonnegativity of potential:

    If Φ_T ≥ 0, then

    ALG≤c OPT+Φ0.\mathrm{ALG} \le c,\mathrm{OPT} + \Phi_0.ALG≤cOPT+Φ0​.

Insight: A potential function is a bookkeeping device that allows you to “move” cost between time steps. The proof succeeds when the potential changes cancel (telescope), leaving only endpoints. A good visualization is literally a stack of blocks that move left/right, showing cancellation as you sum.

Key Takeaways #

Common Mistakes #

Practice #

medium

Ski Rental variant: Rent costs r per day, buy costs B. Consider the threshold algorithm: rent for ⌈B/r⌉−1 days, then buy. Prove an upper bound on its competitive ratio.

Hint: Let m = ⌈B/r⌉. Do a case split on whether D < m. Express OPT(D) = min(rD, B) and compare to ALG(D).

Show solution

Let m = ⌈B/r⌉.

OPT(D) = min(rD, B).

ALG rents for m−1 days and buys on day m if needed.

Case 1: D < m.

ALG(D) = rD = OPT(D), ratio 1.

Case 2: D ≥ m.

ALG(D) = r(m−1) + B.

Since m = ⌈B/r⌉, we have (m−1) < B/r, so r(m−1) < B.

Thus ALG(D) < B + B = 2B = 2·OPT(D) (because OPT(D)=B when D≥m).

So the algorithm is 2-competitive (more tightly, < 2).

easy

Paging warm-up: Let k=2 and consider the request sequence A, B, C, A, B, C, … (repeat). Simulate LRU for the first 9 requests and count misses. What is OPT’s miss count for the same prefix? (You may reason rather than fully compute OPT.)

Hint: With k=2, LRU keeps the two most recently used pages. The repeating pattern of 3 distinct pages forces frequent evictions. For OPT, argue a lower bound: cache size 2 cannot hold all 3 pages, so every third request must miss in steady state.

Show solution

LRU simulation (cache shown as most-recently-used order):

  1. A miss, cache {A}

  2. B miss, cache {B,A}

  3. C miss, evict A, cache {C,B}

  4. A miss, evict B, cache {A,C}

  5. B miss, evict C, cache {B,A}

  6. C miss, evict A, cache {C,B}

  7. A miss, evict B, cache {A,C}

  8. B miss, evict C, cache {B,A}

  9. C miss, evict A, cache {C,B}

So LRU misses on all 9 requests.

For OPT with k=2 on a 3-cycle, OPT still must miss frequently because it can only hold 2 of 3 pages. In steady state, at least 1 of each block of 3 requests must miss, giving a lower bound of ≥ 3 misses for 9 requests. In fact, OPT can do no better than 9 as well in this exact alternating-with-3 pattern under k=2? Reason carefully: because every request is to the page not in cache if OPT keeps the other two, OPT will also miss every time. Indeed, whichever 2 pages OPT holds, the next request is the third page at some point, forcing a miss each step in this strict cycle. Thus OPT also has 9 misses on the first 9 requests, so the ratio here is 1.

hard

Phase argument practice: With cache size k, define phases as ‘maximal contiguous blocks containing at most k distinct pages’. Prove: the number of phases P satisfies P−1 ≤ OPT(σ).

Hint: Look at two consecutive phases. Show that their union contains at least k+1 distinct pages, and argue that OPT must miss at least once somewhere across the boundary because its cache holds only k pages.

Show solution

Let phases be maximal blocks with ≤ k distinct pages. Consider boundary between phase i and phase i+1. Because phase i is maximal, the first request of phase i+1 is to a page not among the distinct pages of phase i; otherwise, phase i could be extended while still using ≤ k distinct pages.

Therefore, the union of distinct pages in phases i and i+1 has size at least k+1.

OPT’s cache holds only k pages, so it cannot contain all k+1 pages simultaneously at the moments they are requested. Hence, among the requests spanning the boundary (i plus the first request of i+1, and possibly more), OPT must incur at least one miss attributable to the inability to hold all k+1 pages.

Thus each boundary forces ≥ 1 OPT miss. With P phases, there are P−1 boundaries, so P−1 ≤ OPT(σ).

Connections #

Next nodes that commonly build on this:

Quality: B (4.0/5)

← back to treebrowse all →