Skip to content
Home » Competitive Analysis

Competitive Analysis

📘 Competitive Analysis (Introduction)

Competitive Analysis is a method used to evaluate the performance of online algorithms by comparing them with an optimal offline algorithm.

👉 It measures how good an online algorithm is, even when it does not know future inputs.

📌 Online Algorithm vs Offline Algorithm

Online Algorithm

  • Makes decisions step-by-step
  • Does NOT know future inputs
  • Example:
    • Paging/caching
    • Scheduling jobs as they arrive
    • Online shopping order matching
    • Load balancing on the fly

Offline Algorithm

  • Knows the entire sequence of inputs in advance
  • Can make perfect decisions
  • Considered optimal (OPT)

📘 What Competitive Analysis Does

Competitive Analysis compares:

[
\text{Cost of Online Algorithm (A)} \quad vs \quad \text{Cost of Optimal Offline Algorithm (OPT)}
]

An online algorithm A is c-competitive if:

[
A(I) \leq c \cdot OPT(I) + k
]

for every input sequence (I).

Where:

  • A(I) = cost of online algorithm on input I
  • OPT(I) = cost of optimal offline algorithm
  • c = competitive ratio
  • k = constant

🎯 Competitive Ratio

Competitive Ratio:

[
\text{Competitive Ratio} = \frac{A(I)}{OPT(I)}
]

  • If ratio = 1 → A is as good as optimal
  • Smaller ratio = better algorithm
  • Ratio ≥ 1 always (cannot beat OPT)

📘 Why Competitive Analysis?

Because:

  • Many real-world algorithms do NOT know future inputs
  • Worst-case analysis is too pessimistic
  • Average-case analysis needs probability
  • Amortized analysis assumes operations sequence, not input unpredictability

Competitive analysis measures performance in adversarial conditions.

📘 Applications of Competitive Analysis

Competitive Analysis is essential in:

  1. Paging / Caching Algorithms
    • FIFO, LRU, LFU
  2. Load Balancing
  3. Task Scheduling
  4. Online Matching
  5. Online Rent-or-Buy Problems
  6. Online Search Problems
  7. Online Data Structures

📘 Classic Examples of Competitive Analysis

✔ Example 1: Paging (Cache Replacement)

In caching, we want to minimize page faults.

Algorithms:

  • FIFO (First-In-First-Out)
  • LRU (Least Recently Used)
  • LFU (Least Frequently Used)

Competitive Ratios:

  • FIFO: competitive ratio = k (cache size)
  • LRU: competitive ratio = k
  • OPT: Belady’s optimal (offline)

LRU is often near optimal despite no future knowledge.

✔ Example 2: The Ski Rental Problem (Rent-or-Buy Problem)

You can:

  • Rent skis for ₹100 per day
  • Buy skis for ₹3000

Without knowing how many days you will ski.

Online strategy:

  • Rent until the total rental cost equals buying cost
  • Then buy

Competitive Ratio = 2

Meaning:

  • Online algorithm costs ≤ 2 × OPT

✔ Example 3: Online Load Balancing

Tasks arrive one by one.
You must assign each task to a machine immediately.

Goal: minimize maximum load.

Greedy online algorithm can be shown to be 2-competitive.

📘 Why Competitive Analysis Works

  • Online algorithm is compared with best possible offline solution
  • It does NOT assume randomness
  • It does NOT assume worst-case adversarial input
  • Gives realistic performance guarantee even without future knowledge

📘 Key Points (For Exams)

  • Competitive analysis evaluates online algorithms
  • Compares cost of online algorithm with optimal offline algorithm
  • Competitive Ratio:
    [
    \frac{A(I)}{OPT(I)}
    ]
  • Algorithm is c-competitive if its cost ≤ c × OPT
  • Important examples: LRU, FIFO, Ski Rental, Load Balancing
  • Does NOT require probability (unlike average case)
  • Does NOT require amortization (unlike amortized analysis)

🎯 Summary (Short Notes)

  • Competitive Analysis: worst-case comparison of online algorithms to optimal offline algorithms
  • Competitive Ratio measures relative performance
  • Used in caching, scheduling, load balancing, rent-or-buy problems
  • Online algorithms = no future knowledge
  • Offline algorithms = complete future knowledge