Wait, What?
“Online algorithm” does not mean “an algorithm on the internet.”
In algorithm design, online describes a problem in which information arrives over time and decisions may have to be made before the future is known. The difficult part is not connectivity. It is commitment under incomplete information.
Quick Answer
Learn online algorithms through the sequence offline version → information restriction → decision point → irreversible consequence → adversarial sequence → offline optimum → competitive ratio → randomized or predictive extensions. The central learning question is: what can a decision rule guarantee when it must act before seeing the rest of the input?
1. First Build the Offline Benchmark
Before studying an online algorithm, solve the imaginary version in which the future is completely visible. That offline optimum becomes the benchmark. Without it, “good online decision” is too vague.
- What would you do if every future request were already known?
- Which decisions could be postponed?
- Which decisions become irreversible in the online model?
- What information has disappeared when we move from offline to online?
This comparison teaches that online difficulty often comes from missing information rather than from the underlying combinatorial structure alone.
2. The Classic First Model: Ski Rental
Imagine skis can be rented day by day or bought once. If you knew exactly how many days you would ski, the decision would be easy. Online, you do not know when skiing will stop. Buying too early wastes money if the season ends immediately; renting too long wastes money if skiing continues for many days.
The educational value is not the skis. It is the structure: pay-as-you-go versus commit-now, with an unknown horizon. Once the learner sees that skeleton, the same reasoning can be transferred to caching, server provisioning, leases, subscriptions and other commitment problems.
3. Competitive Analysis Changes the Question
Competitive analysis compares an online algorithm with an ideal offline algorithm that knows the future. Instead of asking whether the online algorithm makes the optimal decision on every sequence, we ask whether its total cost or value can be bounded relative to the offline optimum across all allowed sequences.
The Simons Institute describes this framework as comparing decisions made without knowledge of the future with the best decisions in hindsight. See Simons Institute: Competitive Analysis of Online Algorithms.
4. Learn the Adversary Without Turning It Into a Villain
In worst-case online analysis, the input sequence is treated as if it could be chosen to expose the algorithm’s weakness. This “adversarial” model is a mathematical stress test. It does not imply that a malicious person is literally generating requests.
Ask the learner to design the worst continuation after each online choice. If the algorithm commits now, what sequence would make that choice painful? If it waits, what sequence punishes waiting? This turns competitive analysis into a game of distinguishing unavoidable uncertainty from avoidable bad strategy.
5. The Core Proof Pattern
- Define the online algorithm precisely.
- Define the offline optimum.
- Partition or charge the online cost to events that OPT must also pay for.
- Bound the online total by a constant or function times OPT, possibly plus a fixed additive term.
- Construct a difficult sequence showing whether the bound is tight or close to tight.
This proof structure is more important than memorising individual competitive ratios. It is the reusable reasoning machinery.
6. Online Does Not Mean Greedy
Many online algorithms make locally immediate decisions, so they can look greedy. But the concepts are different. A greedy algorithm chooses according to a local rule; an online algorithm operates under sequential information constraints. A greedy algorithm may be offline if it sees the entire input first. An online algorithm may use sophisticated state, randomization or optimisation rather than a simple greedy choice.
7. Online Does Not Mean Streaming
Online algorithms focus on when decisions must be made. Streaming algorithms focus on how much memory is available while data passes by. A streaming algorithm may summarize a huge stream without making irreversible operational decisions; an online algorithm may store substantial history but still be unable to see the future. The next article in this batch owns the streaming model.
8. Deterministic, Randomized and Predictive Models
Once the deterministic model is understood, advanced learners can ask whether randomization improves guarantees, whether requests are adversarial or drawn from a distribution, and whether predictions can be incorporated without making the system fragile when predictions are wrong.
Cornell’s advanced algorithms materials use online matching and ski rental as examples of online analysis, and the Simons Institute connects competitive analysis to broader online optimisation methods. See Cornell CS 6820 lecture schedule and notes.
9. Common Learning Failure States
- Thinking “online” simply means real-time software.
- Comparing the algorithm with another weak online strategy instead of the offline optimum.
- Using future information inside a supposedly online rule.
- Confusing average performance with a worst-case competitive guarantee.
- Assuming adversarial analysis predicts typical real-world behaviour.
- Quoting a competitive ratio without stating the input model and cost objective.
- Ignoring whether decisions can be reversed.
10. The Scaffold-Fade Learning Ladder
- Level 1: solve a small offline instance with the future fully visible.
- Level 2: hide future requests and record when a decision becomes unavoidable.
- Level 3: compare two simple online rules on hand-built sequences.
- Level 4: construct adversarial sequences.
- Level 5: derive a competitive bound using a charging or phase argument.
- Level 6: compare deterministic and randomized strategies.
- Level 7: analyse a real system where prediction, stochastic information or changing costs complicate the classical model.
For novices, use worked examples that label the functional subgoals: identify decision point, reveal new information, update state, compare with offline. Programming-education research supports explicit subgoal structure when learners are first acquiring a procedural schema, while later independent reconstruction remains essential. See Margulieux, Morrison and Decker (2020).
11. A Transfer Set
After ski rental, give learners several superficially different situations and ask whether they share the same online structure: caching pages, accepting requests with limited capacity, assigning jobs that arrive over time, choosing when to reserve resources, or deciding when to replace equipment. The goal is not to force every problem into ski rental. It is to learn to identify the information boundary and commitment point.
12. Immediate, Delayed and Professional Checks
- Immediate: explain what information the algorithm lacks at each decision.
- Delayed: reconstruct the competitive-analysis benchmark without notes.
- Transfer: recognise a new problem as online even when it has different vocabulary.
- Counterexample: build a sequence that punishes a naive rule.
- Professional: state whether a worst-case competitive guarantee, stochastic model or empirical workload study is the most relevant evidence.
13. AI Assistance Boundary
Use AI to generate candidate adversarial sequences only after the learner has proposed a strategy and predicted its weakness. Then require the learner to verify whether the sequence is legal and whether the claimed ratio follows. The key reasoning step is not producing a long trace; it is understanding which missing future information creates the decision risk.
Professional Direction
Advanced online algorithms extend into matching, scheduling, resource allocation, caching, primal-dual methods, randomized strategies and algorithms with predictions. Real systems may also use probabilistic forecasts rather than pure worst-case models. A professional should therefore preserve the boundary between theorem and environment: what was guaranteed under adversarial inputs, what assumed a distribution, and what was only observed in data.
Algorithm-learning rule: online algorithms become understandable when the learner can name exactly what is known now, what remains unknowable, which decision cannot wait and how performance will be judged against a future-aware benchmark.
eduKate Sengkang 