Foundations‎ > ‎

## Asymptotic Notations

### `f(n) = Θ(g(n))`

There exist positive constants `c``1`, `c``2`, and `n``0` such that

`0 ≤ c``1``g(n) ≤ f(n) ≤ c``2``g(n) for all n ≥ n``0``.`

We say `g(n)` is an asymptotically tight bound for `f(n)` if `f(n) = Θ(g(n))`. Informally we can say, as far as time complexity or order of growth, these functions are equal.

### - O notation -

`f(n) = O(g(n))`

There exist positive constants c and n0 such that

`0 ≤ f(n) ≤ cg(n) for all n ≥ n``0``.`

We say `g(n)` is an asymptotic upper bound for `f(n)` if `f(n) = O(g(n))`.

### - Ω notation -

`f(n) = Ω(g(n))`

There exist positive constants c and n0 such that

`0 ≤ cg(n) ≤ f(n) for all n ≥ n``0``.`

We say `g(n)` is an asymptotic lower bound for `f(n)` if `f(n) = Ω(g(n))`.

### - o notation -

`f(n) = o(g(n))`

For any positive constant `c > 0`, there exists a constant

`n``0`` > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ n``0``.`

We say `f(n)` is asymptotically smaller than `g(n)` if `f(n) = o(g(n))`. We can also express this as the following limit

`lim``n→∞``(f(n)/g(n)) = 0`

### - ω notation -

`f(n) = ω(g(n))`

For any positive constant `c > 0`, there exists a constant

`n``0`` > 0 such that 0 ≤ cg(n) < f(n) for all n ≥ n``0``.`

We say `f(n)` is asymptotically bigger than `g(n)` if `f(n) = ω(g(n))`. We can also express this as the following limit.

`lim``n→∞``(f(n)/g(n)) = ∞`

### - Properties -

#### Transitivity:

``````  f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n))
f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n))
f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n))
f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))
f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = ω(h(n))```
```

#### Reflexivity:

``````  f(n) = Θ(f(n))
f(n) = O(f(n))
f(n) = Ω(f(n))```
```

#### Symmetry:

```   f(n) = Θ(g(n)) iff g(n) = Θ(f(n)) ```

#### Transpose symmetry:

``````  f(n) = O(g(n)) iff g(n) = Ω(f(n))
f(n) = o(g(n)) iff g(n) = ω(f(n))``````

### - Informal Comparison -

``````  f(n) = O(g(n)) ≈ a ≤ b
f(n) = Ω(g(n)) ≈ a ≥ b
f(n) = Θ(g(n)) ≈ a = b
f(n) = o(g(n)) ≈ a < b
f(n) = ω(g(n)) ≈ a > b``````

### - Note -

From the definitions of `Θ`, `O`, and `Ω` notations we can conclude the following:

`  * For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n)).`
```   * If f(n) = O(g(n)) then g(n) = Ω(f(n)) and vice versa.```