Time Complexity

Time complexity is a way to compare two or more algorithms based on their duration. This comparison is independent of language, hardware, etc. and is instead based on the code itself.

To analyse the time complexity of an algorithm with input $n$, assume the input size n approaches infinity. Eventually, some parts of the rule matter more as n gets bigger than others.

Time complexity uses asymptotic notation, which filters a formula by two simple rules:

• Drop all constants
• Only keep the ‘highest’ term, the term that increases the most

Operations on asymptotic notation should only take the biggest factor for all operations* . E.g. $\frac{3n^2+{\log }_{2}n}{n^2}=O(1)$ , because as n → ∞, only $n^2$ matters

Common Operations §

Command	Time complexity
Statements	$O(1)$ constant
Conditional statements	$O(1)$ constant
Loops	$O(n)$ linear
Nested loops	$O(n^c)$ polynomial
Divide-and-Conquer	$O(nlog(n))$ loglinear or quasilinear