What are online algorithms and competitive analysis?

Online algorithms make decisions without knowing future input, unlike offline algorithms with complete information. Competitive ratio compares online algorithm's cost to optimal offline solution. Examples: Paging/caching - LRU is k-competitive; Ski rental - rent vs buy is 2-competitive; Load balancing - greedy is 2-competitive. Lower bounds prove limits. Randomization can improve competitive ratios. Real applications: caching, scheduling, financial trading, resource allocation.