Online vs Offline Algorithms: What is the Difference?
Learn the difference between online and offline algorithms, competitive ratio, and real examples like LRU caching for interviews.
Expected Interview Answer
An online algorithm processes input piece by piece as it arrives, making irrevocable decisions without knowledge of future input, while an offline algorithm has the entire input available up front and can analyze it all before producing a result.
A classic online example is a caching eviction policy like LRU, which must decide what to evict the instant a cache miss happens, with no knowledge of what will be requested next. A classic offline example is standard sorting, or the offline version of a scheduling problem where all jobs and their times are known in advance, letting the algorithm compute a globally optimal plan before execution starts. Online algorithms are evaluated using competitive analysis, comparing their performance against an optimal offline algorithm that has full foresight, expressed as a competitive ratio. Real systems are frequently forced into the online setting — a router does not know future packets, and a stock-trading algorithm does not know future prices — so online algorithms trade optimality for the ability to function under uncertainty in real time.
- Online algorithms operate under real-time uncertainty (no future knowledge)
- Offline algorithms can compute a globally optimal solution given full input
- Competitive ratio quantifies how close an online algorithm gets to offline-optimal
- Most real-world streaming/live systems are inherently online
AI Mentor Explanation
An online algorithm is like a captain setting the field ball by ball, having to decide where fielders stand before seeing how the batter will actually play the next delivery. An offline algorithm is like a commentator reviewing the entire innings after it finished and declaring, with full hindsight, exactly which field placement would have prevented the most runs. The captain’s live decisions are judged by how close they come to that hindsight-optimal plan, which is essentially a competitive ratio. No matter how skilled, the live captain can never guarantee matching the offline-optimal field because the next ball’s outcome is fundamentally unknown in the moment.
Step-by-Step Explanation
Step 1
Identify input availability
Online: input arrives incrementally, one piece revealed at a time. Offline: the full input is known before the algorithm starts.
Step 2
Note the decision constraint
Online algorithms commit to decisions immediately and cannot revise them once made; offline algorithms can plan globally first.
Step 3
Apply competitive analysis for online algorithms
Compare an online algorithm’s worst-case performance to an optimal offline algorithm, expressed as a competitive ratio.
Step 4
Match the setting to the real system
Real-time systems (caching, routing, live scheduling) are inherently online; batch systems (offline sorting, precomputed schedules) can be offline.
What Interviewer Expects
- Define both clearly with the key distinction: future knowledge availability
- Give a correct real-world online example (LRU cache, live scheduling)
- Give a correct offline example (batch sorting, precomputed optimal schedule)
- Mention competitive ratio as the standard way to evaluate online algorithms
Common Mistakes
- Confusing “online” here with “internet-connected” rather than incremental-input processing
- Assuming an online algorithm can always be made as good as an offline one
- Not knowing what a competitive ratio measures
- Failing to give a concrete real-world example of each
Best Answer (HR Friendly)
“An online algorithm has to make decisions as data comes in, without knowing what is coming next, like a cache deciding what to evict on a miss. An offline algorithm gets to see the whole picture upfront, like sorting a fixed list, and can plan the best possible solution before doing any work. Most real-time systems I have built are online by necessity, since the future genuinely is not known yet.”
Code Example
from collections import OrderedDict
class LRUCache:
"""Online algorithm: decides eviction using only past access history."""
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def access(self, key):
if key in self.cache:
self.cache.move_to_end(key)
else:
if len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # evict least recently used
self.cache[key] = True
def belady_offline_evict(future_requests, cache, capacity):
"""Offline algorithm: knows the full future sequence, evicts the key
used furthest in the future (or never again) -- provably optimal."""
if len(cache) < capacity:
return None
farthest, evict_key = -1, None
for key in cache:
if key not in future_requests:
return key
next_use = future_requests.index(key)
if next_use > farthest:
farthest, evict_key = next_use, key
return evict_keyFollow-up Questions
- What is a competitive ratio, and how is it computed for an online algorithm?
- Why is Belady’s algorithm (optimal eviction) impossible to implement online?
- Can you think of a problem where the online and offline optimal solutions are actually the same?
- How would you design an online algorithm that approximates an offline-optimal solution?
MCQ Practice
1. What best defines an online algorithm?
Online algorithms make irrevocable decisions as each piece of input arrives, with no visibility into future input.
2. What is a competitive ratio used for?
The competitive ratio quantifies how much worse an online algorithm can perform compared to an offline algorithm with full foresight.
3. Which of these is a classic example of an online algorithm?
LRU cache eviction must decide what to evict as each access happens, with no knowledge of future accesses.
Flash Cards
What distinguishes an online algorithm from an offline one? — An online algorithm processes input incrementally with no future knowledge; an offline algorithm has the full input available upfront.
Give a classic online algorithm example. — LRU cache eviction, which must decide immediately on each cache miss.
Give a classic offline algorithm example. — Standard sorting, or Belady’s optimal cache eviction, which needs the full future access sequence.
How are online algorithms formally evaluated? — Using competitive analysis, expressed as a competitive ratio against an optimal offline algorithm.