Complexity theory focuses on classifying computational problems by their resource usage—primarily time and space.
Asymptotic behaviour represents the growth of the function when the size of input is large.
For example \(f(x) = 2x^{2}+ 5x\) and \(g(x) = 4x^{2}-7x\) are asymptotically equivalent. This occurs as when \(x\) becomes non-trivial, all other terms are minimised in comparison to \(x^2\).
Symbolically when \[ \lim_{x \to \infty}{\frac{f(x)}{g(x)}} = 1 \] this relation may be denoted as \[ f \sim g \]
In the context of algorithms, these complexity relations are stated with Big O notation.
When analysing Recurrence relations the Master theorem provides an asymptotic analysis of their behaviour.