Online Algorithms

Why Online Algorithms Matters

You need a tool each day, but do not know how many days you will keep using it. Renting costs 1 per day; buying costs B once and makes later use free. Buying immediately is wasteful if use stops tomorrow. Renting forever is wasteful if requests keep arriving. The decision must be made while the future is still hidden.

An online algorithm receives requests one at a time and serves each request using only information already revealed, plus explicitly allowed prior knowledge. Its choices may be irreversible or costly to undo. The central issue is information, not whether the program is connected to the internet or runs especially quickly. Caching, resource allocation, admission decisions, scheduling, and rent-or-buy choices all expose this kind of uncertainty.

We will use discrete ski rental as a complete worked example of competitive analysis and adversarial inputs. The name is conventional; the same mathematical tradeoff can represent many repeated-use services. We specify the model exactly, implement a causal threshold policy, compare it with an offline optimum, prove its worst-case factor, and show why no deterministic policy can improve that factor under these rules.

The three programs simulate request arrivals deterministically. Their policy object receives the buy price and a threshold, then only a next_request call per arrival. It never receives the final horizon. A separate driver records completed prefixes, computes hindsight comparisons, and prints exact rational ratios. This separation is essential: an evaluator may know the whole test input, but an online decision-maker may not use that knowledge.

Core Concepts and Terminology

Let $\sigma=(r_1,\ldots,r_D)$ be a request sequence. A deterministic online algorithm must make the same decisions on any two inputs that share the same revealed prefix, until the inputs diverge. It may remember the entire past; small memory is not part of the definition. Streaming algorithms add particular processing/memory goals, and real-time algorithms add timing requirements—neither term by itself supplies an online competitive guarantee.

For a minimization problem, write $\operatorname{ALG}(\sigma)$ for the online cost and $\operatorname{OPT}(\sigma)$ for the least cost of a feasible offline solution that knows the entire sequence. Resources, initial state, service obligations and permitted actions must match unless an explicit resource-augmentation model says otherwise. A low cost achieved by skipping requests is not a valid comparison.

A common general guarantee is

$$\operatorname{ALG}(\sigma)\le c\,\operatorname{OPT}(\sigma)+\beta\qquad\text{for every allowed }\sigma,$$

where c and the additive constant $\beta$ do not depend on the particular sequence. This lesson uses the strict multiplicative convention, $\beta=0$, for its exact ski-rental factors. Allowing an arbitrary B-dependent additive term for a single rent-or-buy episode can weaken the comparison greatly: buying immediately always satisfies $\operatorname{ALG}\le\operatorname{OPT}+B$, despite having a poor strict ratio on short episodes. State the convention before comparing claimed factors.

For positive OPT, the strict competitive ratio is the supremum of $\operatorname{ALG}(\sigma)/\operatorname{OPT}(\sigma)$ over all allowed inputs. One observed ratio is a measurement on one input, not a guarantee for every input. When both costs are zero, division is undefined; the empty-input inequality is checked directly instead. If OPT can be zero while ALG is positive, no finite strict multiplicative factor covers that input.

Our concrete model has known positive integer buy price B, rent price 1 per request-day, an initially unowned item, no resale, and an unknown nonnegative integer duration D. On each arriving day, the policy either rents for 1 or buys for B before serving that day's request; buying incurs no rental charge on that same day, and later requests cost zero. It cannot spend after the stream ends. The offline solution either rents every day or buys on the first needed day, so

$$\operatorname{OPT}(D)=\min(D,B).$$

The threshold policy with $\tau\ge1$ rents the first $\tau-1$ arriving days and buys on day $\tau$ if that request arrives. Code threshold 0 means never buy. A request on day $\tau$ is already visible when the decision is made; only subsequent requests and the stopping time remain unknown. The first diagram shows two futures sharing their first three decisions.

How Online Algorithms Works, Step by Step

Build one policy instance from known price B and a chosen threshold $\tau$. It stores only the number of arrivals seen, rentals paid, ownership state, and cumulative online cost. It receives no horizon or offline-optimum parameter.

1. Validate the teaching input. Buy price satisfies $1\le B\le64$ and threshold satisfies $0\le\tau\le128$. The driver accepts $0\le D\le256$ arrivals so complete traces remain manageable. These trace limits do not redefine the theoretical problem: the competitive proofs consider arbitrary finite durations, and the printed “unbounded” result for never buying refers to that unbounded-horizon model.
2. Initialize once. Seen days, rentals, and cost start at zero; ownership is false. No arrival means no action and no purchase. The offline cost is also zero, so the final ratio is printed as NA rather than evaluated.
3. Serve the next arrival. Increment the seen-day counter. If already owned, choose OWNED with zero incremental cost. Otherwise, if the threshold is zero or the current day is earlier than the threshold, choose RENT, pay 1, and increment rentals. Otherwise choose BUY, pay B, and set ownership true.
4. Record the resulting online state. Add the incremental charge once and return a new snapshot. Ownership never changes back to false. Once a purchase happens, all later requests incur zero extra charge. A day is served exactly once, with no simultaneous rental and purchase fee.
5. Audit separately. The driver computes prefix offline cost $\min(d,B)$ after d arrivals and formats the ratio of the recorded online cost to that benchmark. After the stream stops it prints the final ratio, the mathematically derived worst-case factor for the chosen threshold, and its earliest worst-case purchase-day witness if finite. None of those audit values feeds back into the policy.

For $B=4$ and $\tau=4$, days 1–3 rent. When day 4 arrives, the policy buys for 4, increasing cumulative cost from 3 to 7. Day 4 is served by the purchase; there is no additional rental fee. If days 5 or 6 arrive, ownership serves them for free. The decision on day 4 is identical whether the stream ends immediately afterward or continues for years.

The audit also compares never buying, buying immediately, buying at B, and buying at $B+1$ on the same completed horizon. It uses closed-form post-hoc cost formulas, which are appropriate for evaluation but would be future leakage if used to select an earlier action from the final D. The controller's interface and the prefix tests keep these roles separate.

flowchart TD
    A["Construct policy from known buy price and threshold"] --> B["Initialize seen days, rentals, cost, ownership"]
    B --> C{"Another request arrives?"}
    C -->|No| D["Driver computes final hindsight audit"]
    C -->|Yes| E["Increment seen-day counter"]
    E --> F{"Already owned?"}
    F -->|Yes| G["Serve using ownership; spend 0"]
    F -->|No| H{"Never-buy threshold or day below threshold?"}
    H -->|Yes| I["Rent for 1; increment rentals"]
    H -->|No| J["Buy for B; mark owned"]
    G --> K["Record online state; driver audits prefix separately"]
    I --> K
    J --> K
    K --> C

Worked Example with a Full Trace

Take buy price $B=4$, threshold $\tau=4$, and a test stream that happens to last six request-days. The driver knows the test duration; the policy sees only successive arrival calls. Initially cost=0, rented=0, owned=false.

• Day 1: not owned, and $1\lt4$, so RENT. Pay 1; rented=1, owned=false, cost=1. Prefix OPT is $\min(1,4)=1$, so the ratio is $1/1$.
• Day 2: RENT again. Pay 1; rented=2, owned=false, cost=2. Prefix OPT=2 and ratio $1/1$.
• Day 3: RENT again. Pay 1; rented=3, owned=false, cost=3. Prefix OPT=3 and ratio $1/1$.
• Day 4: $4\lt4$ is false, so BUY before serving. Pay 4; rented remains 3, owned=true, cost=$3+4=7$. Prefix OPT=4 and ratio $7/4$.
• Day 5: OWNED. Pay 0; rented=3, owned=true, cost=7. Prefix OPT=4 and ratio $7/4$.
• Day 6: OWNED again. Pay 0; all state remains the same except seen-day count. Final online cost=7, offline cost=4, ratio $7/4$.

The offline cost 4 is feasible because an offline planner knowing D=6 could buy on day 1. The online policy could also buy immediately, but it would then pay 4 on a one-day episode whose offline cost is only 1. Offline knowledge permits different first decisions on different futures; a valid deterministic online policy must have the same first decision whenever its allowed initial information and first request are identical.

The worst ratio for threshold 4 is already reached if the stream ends on day 4. Its trace through day 4 is identical to the first four rows above. Ending at day 3 instead yields online=offline=3. This is the adversarial tension: stopping just after the purchase exposes both earlier rental payments and the purchase charge.

For the completed six-day input, four post-hoc comparisons are:

• Never buy: cost 6, observed ratio $6/4=3/2$, but the worst strict ratio over unbounded horizons is unbounded.
• Buy immediately: cost 4, observed ratio 1, but worst ratio 4 at horizon 1.
• Buy on day 4: cost 7, observed ratio $7/4$, and worst ratio $7/4$.
• Buy on day 5: cost 8, observed ratio 2, and worst ratio 2 at horizon 5.

Buying immediately looks best on this single long input, but buying at B has the best deterministic worst-case guarantee. Never buying also looks better than the balanced policy on this particular six-day stream; that does not contradict its unbounded worst ratio on arbitrarily long streams. The diagrams and printed audit deliberately keep observed performance separate from the universal claim.

Implementation in Python, C++, and Java

All three panels are standalone programs with identical policy state transitions, validation, sample input, exact fraction formatting, and post-hoc audits. Python needs 3.9 or later; C++ uses C++17; Java uses Java 8 or later and should be saved as Main.java. Run python3 main.py; compile/run C++ with g++ -std=c++17 -O2 main.cpp -o online-model then ./online-model; compile/run Java with javac Main.java then java Main.

The public driver is simulate(buy,threshold,horizon). Validation checks BUY, THRESHOLD, and HORIZON in that order. Accepted limits are buy price 1–64, threshold 0–128, and horizon 0–256. Python rejects booleans, floats, nulls and strings where exact integers are required; C++/Java signatures use integer parameters. Errors raise exceptions. Under these limits, recorded costs and all exact-ratio arithmetic are comfortably within the fixed integer types; C++/Java store costs in wide integer fields.

The Policy constructor accepts only buy price and threshold. Its request method takes no duration, remaining-length, or OPT argument. The driver calls it once for each arrival. Step records the state after that arrival, and later steps do not overwrite earlier snapshots. Result stores the completed trace and separate offline metadata. The code's mutable record types are used as snapshots; no later policy action mutates an already returned record.

policy_bound/policyBound returns the exact mathematical worst ratio and the purchase-day witness for a positive threshold. A denominator of zero is an internal marker for “unbounded,” never used as a divisor. closed_cost/closedCost is an offline evaluation helper; the controller never calls it. Ratio formatting uses integer greatest common divisors, with NA for the empty episode's undefined $0/0$. It does not use floating-point rounding to assert a bound or compare tight ratios.

The result's horizon is driver metadata, not information supplied to Policy. A production event loop would call the request method when a request actually arrives; the test driver merely generates those calls from a finite sample. The mathematical proof concerns arbitrary horizons beyond the display cap. In particular, “never buy: unbounded” is a statement about that theoretical model, not a claim that costs exceed every finite number inside the driver's 256-request limit.

Verification: each language passed 16,574 configurations, including 16,566 valid and 8 rejected inputs. Full traces compare 1,218,507 daily states, exact ratios, offline optima and bound witnesses. Independent offline enumeration considers every feasible first purchase day plus never buying. Tests include all buy prices 1–64, every finite supported threshold as a worst-day case, boundary horizons, empty input, and seeded random configurations. A separate Python sweep checks all 8,192 positive price/threshold pairs through 256 arrivals, totaling 2,097,152 policy requests, and confirms the minimum worst factor occurs at threshold B within that range. Twenty-five paired-prefix tests compare independently stopped controllers. An exact expectation audit checks the B=2 randomized example below on 256 fixed horizons; this is algebraic evaluation, not a randomized implementation. Nine extra Python cases reject invalid runtime types. C++ passed address/undefined-behavior sanitizer runs; Java compiled with all lint warnings enabled. Full formatted traces agree across languages and sample stdout matches byte for byte. Finite tests support the implementation; the proofs establish the unrestricted guarantee.

from dataclasses import dataclass
from math import gcd

@dataclass
class Step:
    day: int
    action: str
    spent: int
    rented: int
    owned: bool
    cost: int

@dataclass
class Bound:
    numerator: int
    denominator: int  # Zero denotes an unbounded ratio, not a division.
    witness: int

@dataclass
class Result:
    buy: int
    threshold: int
    horizon: int
    steps: list[Step]
    online: int
    offline: int
    bound: Bound

def validate_policy(buy: int, threshold: int) -> None:
    if type(buy) is not int or not 1 <= buy <= 64:
        raise ValueError("BUY")
    if type(threshold) is not int or not 0 <= threshold <= 128:
        raise ValueError("THRESHOLD")

class Policy:
    """Receives arrivals one at a time; it never receives a final horizon."""
    def __init__(self, buy: int, threshold: int):
        validate_policy(buy, threshold)
        self.buy = buy
        self.threshold = threshold  # 0 means never buy.
        self.day = self.rented = self.cost = 0
        self.owned = False

    def next_request(self) -> Step:
        self.day += 1
        if self.owned:
            action, spent = "OWNED", 0
        elif self.threshold == 0 or self.day < self.threshold:
            action, spent = "RENT", 1
            self.rented += 1
        else:
            action, spent = "BUY", self.buy
            self.owned = True
        self.cost += spent
        return Step(self.day, action, spent, self.rented, self.owned, self.cost)

def policy_bound(buy: int, threshold: int) -> Bound:
    validate_policy(buy, threshold)
    if threshold == 0:
        return Bound(0, 0, 0)
    numerator = buy + threshold - 1
    denominator = min(buy, threshold)
    divisor = gcd(numerator, denominator)
    return Bound(numerator // divisor, denominator // divisor, threshold)

def closed_cost(buy: int, threshold: int, horizon: int) -> int:
    # Post-hoc evaluator only; the online Policy never calls this function.
    return horizon if threshold == 0 or horizon < threshold else buy + threshold - 1

def simulate(buy: int, threshold: int, horizon: int) -> Result:
    validate_policy(buy, threshold)
    if type(horizon) is not int or not 0 <= horizon <= 256:
        raise ValueError("HORIZON")
    policy = Policy(buy, threshold)
    steps = [policy.next_request() for _ in range(horizon)]
    return Result(buy, threshold, horizon, steps, policy.cost,
                  min(horizon, buy), policy_bound(buy, threshold))

def ratio(numerator: int, denominator: int) -> str:
    if denominator == 0:
        return "NA"  # Empty input: both costs are zero.
    divisor = gcd(numerator, denominator)
    return f"{numerator // divisor}/{denominator // divisor}"

def bound_text(bound: Bound) -> str:
    return "unbounded" if bound.denominator == 0 else ratio(bound.numerator, bound.denominator)

def witness_text(bound: Bound) -> str:
    return "NA" if bound.denominator == 0 else str(bound.witness)

def format_result(r: Result) -> str:
    lines = [f"B={r.buy} threshold={r.threshold} horizon={r.horizon}"]
    for step in r.steps:
        opt = min(step.day, r.buy)
        lines.append(f"day={step.day} action={step.action} spent={step.spent} "
                     f"rented={step.rented} owned={int(step.owned)} cost={step.cost} "
                     f"prefix_opt={opt} ratio={ratio(step.cost, opt)}")
    lines.append(f"final online={r.online} offline={r.offline} ratio={ratio(r.online, r.offline)}")
    lines.append(f"theory worst={bound_text(r.bound)} witness={witness_text(r.bound)}")
    for label, threshold in [("never", 0), ("immediate", 1),
                              ("balanced", r.buy), ("late", r.buy + 1)]:
        cost = closed_cost(r.buy, threshold, r.horizon)
        bound = policy_bound(r.buy, threshold)
        lines.append(f"audit {label} threshold={threshold} cost={cost} "
                     f"ratio={ratio(cost, r.offline)} worst={bound_text(bound)} "
                     f"witness={witness_text(bound)}")
    return "\n".join(lines)

if __name__ == "__main__":
    print(format_result(simulate(buy=4, threshold=4, horizon=6)))

#include <algorithm>
#include <iostream>
#include <numeric>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct Step {
    int day;
    std::string action;
    int spent, rented;
    bool owned;
    long long cost;
};
struct Bound { long long numerator, denominator; int witness; };
struct Result {
    int buy, threshold, horizon;
    std::vector<Step> steps;
    long long online, offline;
    Bound bound;
};
void validate_policy(int buy, int threshold) {
    if (buy<1 || buy>64) throw std::invalid_argument("BUY");
    if (threshold<0 || threshold>128) throw std::invalid_argument("THRESHOLD");
}
class Policy {
public:
    int buy, threshold, day=0, rented=0;
    long long cost=0;
    bool owned=false;
    Policy(int b, int t) : buy(b), threshold(t) { validate_policy(b,t); }
    Step next_request() {
        ++day; std::string action; int spent;
        if (owned) { action="OWNED"; spent=0; }
        else if (threshold==0 || day<threshold) { action="RENT"; spent=1; ++rented; }
        else { action="BUY"; spent=buy; owned=true; }
        cost+=spent;
        return Step{day,action,spent,rented,owned,cost};
    }
};
Bound policy_bound(int buy, int threshold) {
    validate_policy(buy,threshold);
    if (!threshold) return Bound{0,0,0};
    long long numerator=buy+threshold-1, denominator=std::min(buy,threshold);
    long long divisor=std::gcd(numerator,denominator);
    return Bound{numerator/divisor,denominator/divisor,threshold};
}
long long closed_cost(int buy, int threshold, int horizon) {
    // Post-hoc evaluator; never called by the online Policy.
    return threshold==0 || horizon<threshold ? horizon : buy+threshold-1;
}
Result simulate(int buy, int threshold, int horizon) {
    validate_policy(buy,threshold);
    if (horizon<0 || horizon>256) throw std::invalid_argument("HORIZON");
    Policy policy(buy,threshold); std::vector<Step> steps;
    for (int i=0; i<horizon; ++i) steps.push_back(policy.next_request());
    return Result{buy,threshold,horizon,steps,policy.cost,std::min(horizon,buy),policy_bound(buy,threshold)};
}
std::string ratio(long long numerator, long long denominator) {
    if (!denominator) return "NA";
    long long divisor=std::gcd(numerator,denominator);
    return std::to_string(numerator/divisor)+"/"+std::to_string(denominator/divisor);
}
std::string bound_text(const Bound& b) { return b.denominator ? ratio(b.numerator,b.denominator) : "unbounded"; }
std::string witness_text(const Bound& b) { return b.denominator ? std::to_string(b.witness) : "NA"; }
std::string format_result(const Result& r) {
    std::ostringstream out;
    out << "B=" << r.buy << " threshold=" << r.threshold << " horizon=" << r.horizon << '\n';
    for (const auto& step : r.steps) {
        int opt=std::min(step.day,r.buy);
        out << "day=" << step.day << " action=" << step.action << " spent=" << step.spent
            << " rented=" << step.rented << " owned=" << step.owned << " cost=" << step.cost
            << " prefix_opt=" << opt << " ratio=" << ratio(step.cost,opt) << '\n';
    }
    out << "final online=" << r.online << " offline=" << r.offline << " ratio=" << ratio(r.online,r.offline) << '\n';
    out << "theory worst=" << bound_text(r.bound) << " witness=" << witness_text(r.bound) << '\n';
    std::vector<std::pair<std::string,int>> policies{ {"never",0},{"immediate",1},{"balanced",r.buy},{"late",r.buy+1} };
    for (const auto& entry : policies) {
        int threshold=entry.second; long long cost=closed_cost(r.buy,threshold,r.horizon);
        auto bound=policy_bound(r.buy,threshold);
        out << "audit " << entry.first << " threshold=" << threshold << " cost=" << cost
            << " ratio=" << ratio(cost,r.offline) << " worst=" << bound_text(bound)
            << " witness=" << witness_text(bound) << '\n';
    }
    auto text=out.str(); text.pop_back(); return text;
}
int main() {
    std::cout << format_result(simulate(4,4,6)) << '\n';
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    static final class Step {
        int day, spent, rented; String action; boolean owned; long cost;
        Step(int day, String action, int spent, int rented, boolean owned, long cost) {
            this.day=day; this.action=action; this.spent=spent; this.rented=rented; this.owned=owned; this.cost=cost;
        }
    }
    static final class Bound {
        long numerator, denominator; int witness;
        Bound(long numerator, long denominator, int witness) {
            this.numerator=numerator; this.denominator=denominator; this.witness=witness;
        }
    }
    static final class Result {
        int buy, threshold, horizon; List<Step> steps; long online, offline; Bound bound;
        Result(int buy, int threshold, int horizon, List<Step> steps, long online, long offline, Bound bound) {
            this.buy=buy; this.threshold=threshold; this.horizon=horizon; this.steps=steps;
            this.online=online; this.offline=offline; this.bound=bound;
        }
    }
    static void validatePolicy(int buy, int threshold) {
        if (buy<1 || buy>64) throw new IllegalArgumentException("BUY");
        if (threshold<0 || threshold>128) throw new IllegalArgumentException("THRESHOLD");
    }
    static final class Policy {
        int buy, threshold, day, rented; long cost; boolean owned;
        Policy(int buy, int threshold) { validatePolicy(buy,threshold); this.buy=buy; this.threshold=threshold; }
        Step nextRequest() {
            ++day; String action; int spent;
            if (owned) { action="OWNED"; spent=0; }
            else if (threshold==0 || day<threshold) { action="RENT"; spent=1; ++rented; }
            else { action="BUY"; spent=buy; owned=true; }
            cost+=spent;
            return new Step(day,action,spent,rented,owned,cost);
        }
    }
    static long gcd(long a, long b) {
        while (b!=0) { long r=a%b; a=b; b=r; } return a;
    }
    static Bound policyBound(int buy, int threshold) {
        validatePolicy(buy,threshold);
        if (threshold==0) return new Bound(0,0,0);
        long numerator=buy+threshold-1, denominator=Math.min(buy,threshold);
        long divisor=gcd(numerator,denominator);
        return new Bound(numerator/divisor,denominator/divisor,threshold);
    }
    static long closedCost(int buy, int threshold, int horizon) {
        // Post-hoc evaluator; never called by the online Policy.
        return threshold==0 || horizon<threshold ? horizon : buy+threshold-1;
    }
    static Result simulate(int buy, int threshold, int horizon) {
        validatePolicy(buy,threshold);
        if (horizon<0 || horizon>256) throw new IllegalArgumentException("HORIZON");
        Policy policy=new Policy(buy,threshold); List<Step> steps=new ArrayList<>();
        for (int i=0; i<horizon; ++i) steps.add(policy.nextRequest());
        return new Result(buy,threshold,horizon,steps,policy.cost,Math.min(horizon,buy),policyBound(buy,threshold));
    }
    static String ratio(long numerator, long denominator) {
        if (denominator==0) return "NA";
        long divisor=gcd(numerator,denominator);
        return (numerator/divisor)+"/"+(denominator/divisor);
    }
    static String boundText(Bound b) { return b.denominator==0 ? "unbounded" : ratio(b.numerator,b.denominator); }
    static String witnessText(Bound b) { return b.denominator==0 ? "NA" : Integer.toString(b.witness); }
    static String formatResult(Result r) {
        StringBuilder out=new StringBuilder();
        out.append("B=").append(r.buy).append(" threshold=").append(r.threshold).append(" horizon=").append(r.horizon).append('\n');
        for (Step step : r.steps) {
            int opt=Math.min(step.day,r.buy);
            out.append("day=").append(step.day).append(" action=").append(step.action).append(" spent=").append(step.spent)
               .append(" rented=").append(step.rented).append(" owned=").append(step.owned ? 1 : 0).append(" cost=")
               .append(step.cost).append(" prefix_opt=").append(opt).append(" ratio=").append(ratio(step.cost,opt)).append('\n');
        }
        out.append("final online=").append(r.online).append(" offline=").append(r.offline)
           .append(" ratio=").append(ratio(r.online,r.offline)).append('\n');
        out.append("theory worst=").append(boundText(r.bound)).append(" witness=").append(witnessText(r.bound)).append('\n');
        String[] labels={"never","immediate","balanced","late"}; int[] thresholds={0,1,r.buy,r.buy+1};
        for (int i=0; i<labels.length; ++i) {
            int threshold=thresholds[i]; long cost=closedCost(r.buy,threshold,r.horizon); Bound bound=policyBound(r.buy,threshold);
            out.append("audit ").append(labels[i]).append(" threshold=").append(threshold).append(" cost=").append(cost)
               .append(" ratio=").append(ratio(cost,r.offline)).append(" worst=").append(boundText(bound))
               .append(" witness=").append(witnessText(bound)).append('\n');
        }
        out.setLength(out.length()-1); return out.toString();
    }
    public static void main(String[] args) { System.out.println(formatResult(simulate(4,4,6))); }
}

Identical expected output (each item is one printed line; a theory witness need not equal the current test horizon):

• B=4 threshold=4 horizon=6
• day=1 action=RENT spent=1 rented=1 owned=0 cost=1 prefix_opt=1 ratio=1/1
• day=2 action=RENT spent=1 rented=2 owned=0 cost=2 prefix_opt=2 ratio=1/1
• day=3 action=RENT spent=1 rented=3 owned=0 cost=3 prefix_opt=3 ratio=1/1
• day=4 action=BUY spent=4 rented=3 owned=1 cost=7 prefix_opt=4 ratio=7/4
• day=5 action=OWNED spent=0 rented=3 owned=1 cost=7 prefix_opt=4 ratio=7/4
• day=6 action=OWNED spent=0 rented=3 owned=1 cost=7 prefix_opt=4 ratio=7/4
• final online=7 offline=4 ratio=7/4
• theory worst=7/4 witness=4
• audit never threshold=0 cost=6 ratio=3/2 worst=unbounded witness=NA
• audit immediate threshold=1 cost=4 ratio=1/1 worst=4/1 witness=1
• audit balanced threshold=4 cost=7 ratio=7/4 worst=7/4 witness=4
• audit late threshold=5 cost=8 ratio=2/1 worst=2/1 witness=5

Complexity, Correctness, and Invariants

There are two independent questions: how much computation an arrival requires, and how costly the resulting decisions are compared with hindsight. Constant-time processing does not imply a competitive factor of one.

Feasibility and state invariant. For a positive threshold $\tau$, after d arrivals, if $d\lt\tau$, no purchase has occurred, rented=d, and cost=d. If $d\ge\tau$, exactly $\tau-1$ rentals and one purchase have occurred, ownership is true, and cost=$\tau-1+B$. For the never-buy policy, rented=cost=d and ownership remains false. These claims follow by induction: a pre-threshold request rents once; the threshold request buys once; every later request uses ownership for zero extra cost. Every request is served and no action depends on an unseen request. Thus

$$C_\tau(D)=\begin{cases}D,&D\lt\tau,\\B+\tau-1,&D\ge\tau,\end{cases}\qquad\tau\ge1,$$

while $C_{\mathrm{never}}(D)=D$. The policy is feasible regardless of its competitive quality.

Offline optimum. A plan that never buys costs D. Any plan buying for the first time on day t costs $(t-1)+B\ge B$; when a positive episode is known in advance, buying on day 1 attains B. Therefore $\operatorname{OPT}(D)=\min(D,B)$, including the empty episode where the minimum is zero. This argument enumerates all meaningful offline possibilities rather than assuming the benchmark by inspection.

Exact worst ratio of a threshold. For finite $\tau\ge1$, the maximum ratio over positive horizons is

$$R(\tau)=\sup_{D\ge1}\frac{C_\tau(D)}{\min(D,B)}=\frac{B+\tau-1}{\min(\tau,B)}.$$

To see why the witness is $D=\tau$, consider horizons before and after the purchase. Before $\tau$, the policy only rents. If $D\le B$, that has ratio 1; if $B\lt D\lt\tau$, its ratio is $D/B$ and is strictly below the eventual purchase ratio $(B+\tau-1)/B$. At or after $\tau$, the numerator is constant while the denominator $\min(D,B)$ is nondecreasing, so the largest such ratio occurs first at $D=\tau$. This proves both the upper bound and the adversarial witness. Never buying instead has ratio $D/B$ for $D\ge B$, which grows without bound as D grows.

Choose the balanced threshold. Set $\tau=B$. If $D\lt B$, online and offline both pay D. If $D\ge B$, online pays $2B-1$ while offline pays B. Hence

$$C_B(D)\le\left(2-\frac1B\right)\operatorname{OPT}(D),\qquad R(B)=2-\frac1B.$$

For B=4 this is $7/4$; for B=1 the policy buys on its first request and is exactly optimal. As integer B grows, the factor approaches 2. Renting B days and buying on day $B+1$ instead gives exactly factor 2. Both can be described loosely as “2-competitive,” but their exact discrete factors and purchase timing differ. Continuous-time conventions or non-integer rental units require their own timing model.

Matching deterministic lower bound. Fix any deterministic online policy in this model and present identical daily requests until its first purchase day $\tau$. Along an indefinitely continuing stream, that first day is fixed by its code, known parameters and observed identical history. If it never buys, a long enough horizon gives an arbitrarily bad ratio. Otherwise end the episode on the day it buys, so $D=\tau$. The policy pays $B+\tau-1$; offline pays $\min(\tau,B)$. If $\tau\le B$,

$$R(\tau)=1+\frac{B-1}{\tau}\ge1+\frac{B-1}{B}=2-\frac1B.$$

If $\tau\ge B$,

$$R(\tau)=1+\frac{\tau-1}{B}\ge2-\frac1B.$$

Thus no deterministic online policy has a smaller strict factor under these rules, and threshold B matches the lower bound. The quantifiers matter: for every deterministic policy there is a bad horizon, potentially a different one for each policy. Because a deterministic policy's purchase day can be predicted without private coins, the lower-bound horizon can be fixed in advance for that policy; the argument does not need an adversary observing random outcomes.

Computation and space. The controller performs $\Theta(1)$ word operations per arrival in best, average and worst cases; it has $O(1)$ mutable state. Constructing D snapshots costs $\Theta(D+1)$ work including setup and $O(D+1)$ storage, while an event loop that discards history retains only constant policy state. The four closed-form post-hoc policy cost evaluations use constant arithmetic each. Fraction formatting also computes gcd: with unbounded word-sized parameter magnitudes U, a coarse Euclidean-iteration bound is $O(\log U)$ per formatted ratio, separate from the controller's decision cost; arbitrary-precision bit costs require further accounting. With the small fixed teaching bounds, all these integer values and representations are bounded. None of these runtime statements is the dimensionless competitive guarantee.

Randomization and the adversary. Against an oblivious adversary, a randomized guarantee has the form

$$\mathbb{E}_{\text{private coins}}[C(D)]\le c\,\operatorname{OPT}(D)\qquad\text{for every fixed }D.$$

The expectation is over the policy's randomness, not an assumed input distribution. For a concrete discrete B=2 example, choose threshold 1 with probability $1/3$ and threshold 2 with probability $2/3$, before arrivals and independently of a fixed horizon. At D=1 the expected cost is $2/3+2/3=4/3$, against OPT=1. For every $D\ge2$, expected cost is $2/3+2=8/3$, against OPT=2. Therefore this mixture has expected factor $4/3$, improving on the best deterministic factor $3/2$ for B=2. The programs implement deterministic thresholds only; the test suite audits this small expectation exactly. If an adversary chooses the stopping time after observing the random decision, D is no longer fixed independently of those coins and the same proof cannot simply be reused. Distributional lower-bound methods, including Yao-style arguments, formalize this algorithm-versus-input distinction.

Variants, Pitfalls, and Optimizations

Future leakage can masquerade as a great algorithm. A rule that checks if horizon >= B: buy on day 1 exactly reproduces offline knowledge. On first request, horizons 1 and 6 have the same revealed information but that rule chooses different actions. It is invalid as an online policy. Keep duration, remaining length, future requests and offline-optimum decisions out of the controller. Testing identical prefixes with different suffixes is a practical causality check, though the interface/proof remains the stronger guarantee.

Specify the purchase-day charge. Our threshold is the first request served by buying, so threshold B rents only B−1 days. Buying on day B after already renting that same day changes the cost model. Renting B complete days and buying on the next arrival is threshold $B+1$ and has exact ratio 2. If the stream ends before that next arrival, there is no purchase; never buy merely because a loop has ended. At B=1 the balanced algorithm buys immediately, a useful boundary test for this off-by-one error.

A finite maximum is evidence, not the universal proof. Exhausting horizons up to 256 cannot by itself prove a statement about all durations or establish that never buying is unbounded. The threshold cost formula and monotonic-denominator argument explain why no later horizon produces a larger finite-threshold ratio. Growth of $D/B$ proves unboundedness for never buying. Also, a worst-case upper bound and a matching adversarial lower bound are different claims: a bad example shows the factor cannot be improved for that policy, while the case analysis shows no input is worse.

Use the same benchmark and state. Offline and online must serve the same requests with the same allowed purchase/rental prices and initial ownership. Comparing an unowned online controller with a free pre-owned offline one changes OPT. Lookahead, cancellation, resale, announced duration caps, variable prices, discounts and multiple items all change the problem. Resource augmentation deliberately changes resources, but should be named and analyzed as a different comparison. A small simulator display cap is not a theorem about an announced finite-horizon problem.

Keep ratios, expectations and additive constants straight. Do not divide by zero on an empty episode or replace $0/0$ with a claimed competitive ratio. Do not average a handful of observed ratios and call the result a worst-case factor. For random algorithms against fixed inputs, expectation is over private coins; against random inputs, averaging ratios and taking a ratio of expected costs are generally different quantities. The B=2 mixture proof works because every fixed positive horizon satisfies the same bound. Additive allowances can materially change a single-episode claim, so retain the strict convention when quoting the exact deterministic lower bound here.

Known distributions and predictions are extra assumptions. A stochastic model may optimize expected cost under an arrival distribution instead of the worst sequence. A horizon prediction may justify a different policy, but inaccurate predictions then require a robustness analysis. Learning-augmented methods often separate consistency under accurate advice from worst-case robustness; do not treat the prediction as certain future information while claiming the original adversarial guarantee. An adaptive adversary that observes prior actions may have more power than the oblivious adversary used in a randomized proof.

Other online problems need their own invariants. In paging, cache replacement is online while a future-aware offline eviction rule is a benchmark; phase/potential analyses compare misses under stated capacities and initial caches. In online scheduling, machines and service commitments affect what can be revised. In matching/admission problems, irrevocable commitments change feasibility. A policy can be fast and still uncompetitive, or competitive but expensive to implement. The ski-rental factor does not transfer merely because another application also makes sequential decisions.

Practical optimizations preserve causality. Drop trace storage for a small-state event loop, make prices/units explicit, use checked arithmetic if removing the numeric caps, and record enough audit information to reproduce decisions. Operational costs, minimum contract lengths, resale values and service overhead may dominate an abstract model; incorporate relevant costs before applying its threshold to an actual system. This lesson supplies a mathematical template rather than a universal purchasing rule.

Practice Problems and Real-World Use

Write a sequential offline reference before evaluating the online policy. For a completed rent-or-buy episode, enumerate every feasible first-purchase day and the never-buy plan; their minimum must agree with $\min(D,B)$. Then verify every online prefix: total paid is rentals plus at most one purchase, ownership never reverses, each arrival is served once, and no action occurs after the final arrival.

Test empty input, B=1, thresholds 0/1/B/$B+1$, and durations immediately before/at/after a purchase day. Test long episodes for a never-buy policy and short episodes for an immediate-buy policy. Compare exact fractions using integer arithmetic. For each finite threshold, evaluate its claimed witness $D=\tau$ and check the bound on other horizons. Change the future stopping time while retaining the same prefix; the online state snapshots on that prefix must remain identical.

An adversarial experiment should be separate from the policy. Given a deterministic threshold, the experiment can choose its purchase day as the completed input; the policy must still run one arrival at a time without being told that duration. Plotting observed ratios over D can help find a candidate worst case, but the proof must explain the entire domain. For a randomized extension, fix each test horizon independently of sampled thresholds and record the random seed, trial count and uncertainty; simulation estimates an expectation, whereas the small B=2 calculation above gives an exact one.

The next conceptual steps are amortized charging and potential functions, distributional/Yao lower bounds, paging, online scheduling, resource augmentation, advice complexity and robust use of predictions. Each extension should declare what the algorithm knows, when a decision becomes binding, what OPT may do, and which adversary is allowed. Those modeling choices are part of the theorem, not implementation footnotes.

Primary reading: CMU's Online Algorithms notes develop the rent-or-buy and paging framework, including the discrete threshold convention. MIT's online-algorithm notes discuss competitive analysis and adversarial/game viewpoints. The state-machine interface, exact sample, finite tests and post-hoc audit format above belong to this lesson's implementations.