Definition (Worst case running time) Formally $f(n)=\underbrace{\max}_{\text{input $I$ of size $n$}} (\text{runtime of the algorithm on the input I})$supposing that each elementary operation takes a fixed amount of time to perform. # Properties - It is a property of an [[Algorithm for Computational Problem|algorithm]] that allow us to compare their [[Time complexity of an algorithm|runtime]]. - Independent of - programming language - specific input - machine (computer); unlike [[Runtime of a program]]. # Examples - Quadratic time ($\mathcal{O}(n^{2})$) algorithm: [[Bubble Sort]]. - Logarithmic time ($\mathcal{O}(\log n)$) algorithm: [[Binary Search]]. - Linearithmic time ($\mathcal{O}(n\log n)$) algorithm: [[Merge Sort]].