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.