([Analisi complessità](../../../BSc(italian)/Algoritmi%20e%20Principi%20dell'Informatica/src/08.Analisi%20complessità.md)) # 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](https://www.youtube.com/watch?v=i7vq-HY10hI) .