08.Competitive analysis

(Analisi complessità)

Competitive analysis

Difference between online (real-time) and offline algorithms:

• an online algorithm A executes the given operation without any knowledge of the future incoming operations
• an offline algorithm knows the whole sequence in advance

An online algorithm is $\alpha$-competitive if exists a constant $k$ such that for any incoming sequence of operations $S$ we have that $C_A(S)\le \alpha C_{\text{offline}}+k$ where $C_{\text{offline}}$ is the optimal offline algorithm.

Move to front heuristic

Self-organizing lists. Elements that are accessed frequently will be in front of the list. MTF algorithm is $4$-competive with an offline algorithm (that’s good). In this video MTF is used to cache voxels in a rendering engine .