This survey examines online algorithms, which make decisions without knowing future inputs, leveraging advice to achieve competitive performance. Competitive analysis and regret analysis are explained, along with utility maximization, caching algorithms, and multiplicative weights update algorithms. Key concepts like competitive ratio, regret, utility, and adversary are defined. The survey explores connections to game theory, information theory, and data compression, providing real-world applications in web caching, online learning, and advertising.
