## Asymptotic Notations

**- Θ notation -**

###
`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 n

_{0} 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 n

_{0} 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.
```