 Competitive analysis (online algorithm)

Competitive analysis is a method used to evaluate the performance of online algorithms by comparing them to an optimal offline algorithm. In the context of algorithm design, an **online algorithm** is one that must make decisions based on the information available at the time of the decision, without knowledge of future events or inputs. This contrasts with an **offline algorithm**, which has access to the entire input beforehand and can make optimal decisions based on that complete information.