home
# Computational complexity

Complexity theory focuses on classifying computational problems by their resource usageâ€”primarily time and space.

## Asymptotic complexity

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.

## Recursion complexity

When analysing Recurrence relations the Master theorem provides an asymptotic analysis of their behaviour.