Unlike Big-O notation, which represents only upper bound of the running time for some algorithm, Big-Theta is a tight bound; both upper and lower bound. Tight bound is more precise, but also more difficult to compute.

The Big-Theta notation is symmetric: `f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))`

An intuitive way to grasp it is that `f(x) = Ө(g(x))`

means that the graphs of f(x) and g(x) grow in the same rate, or that the graphs 'behave' similarly for big enough values of x.

The full mathematical expression of the Big-Theta notation is as follows:

Ө(f(x)) = {g: N_{0} -> R and c_{1}, c_{2}, n_{0} > 0, where c_{1} < abs(g(n) / f(n)), for every n > n_{0} and abs is the absolute value }

**An example**

If the algorithm for the input `n`

takes `42n^2 + 25n + 4`

operations to finish, we say that is `O(n^2)`

, but is also `O(n^3)`

and `O(n^100)`

. However, it is `Ө(n^2)`

and it is not `Ө(n^3)`

, `Ө(n^4)`

etc. Algorithm that is `Ө(f(n))`

is also `O(f(n))`

, but not vice versa!

**Formal mathematical definition**

`Ө(g(x))`

is a set of functions.

`Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}`

Because `Ө(g(x))`

is a set, we could write `f(x) ∈ Ө(g(x))`

to indicate that `f(x)`

is a member of `Ө(g(x))`

. Instead, we will usually write
`f(x) = Ө(g(x))`

to express the same notion - that's the common way.

Whenever `Ө(g(x))`

appears in a formula, we interpret it as standing for some anonymous function that we do not care to name. For example the equation `T(n) = T(n/2) + Ө(n)`

, means `T(n) = T(n/2) + f(n)`

where `f(n)`

is a function in the set `Ө(n)`

.

Let `f`

and `g`

be two functions defined on some subset of the real numbers. We write `f(x) = Ө(g(x))`

as `x->infinity`

if and only if there are positive constants `K`

and `L`

and a real number `x0`

such that holds:

`K|g(x)| <= f(x) <= L|g(x)|`

for all `x >= x0`

.

The definition is equal to:

`f(x) = O(g(x)) and f(x) = Ω(g(x))`

**A method that uses limits**

if `limit(x->infinity) f(x)/g(x) = c ∈ (0,∞)`

i.e. the limit exists and it's positive, then `f(x) = Ө(g(x))`

**Common Complexity Classes**

Name | Notation | n = 10 | n = 100 |
---|---|---|---|

Constant | Ө(1) | 1 | 1 |

Logarithmic | Ө(log(n)) | 3 | 7 |

Linear | Ө(n) | 10 | 100 |

Linearithmic | Ө(n*log(n)) | 30 | 700 |

Quadratic | Ө(n^2) | 100 | 10 000 |

Exponential | Ө(2^n) | 1 024 | 1.267650e+ 30 |

Factorial | Ө(n!) | 3 628 800 | 9.332622e+157 |

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow