When we are talking about the efficiency of algorithms, we generally mean the ** asymptotic** efficiency of algorithms. It means how the running time of an algorithm increases with the increase in the size of the input.

The notations we use to describe the asymptotic running time of an algorithm are called **asymptotic notations**. Let’s discuss some of these notations.

# Θ (big theta) notation

For a given function g(n), we denote by Θ(g(n)) the set of functions

Θ(g(n)) = {f(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}}

A function f(n) belongs to the set Θ(g(n)) if there exist positive constants c_{1} and c_{2} such that it can be “sandwiched” between c_{1}g(n) and c_{2}g(n) for sufficiently large n.

Since Θ(g(n)) is a set, we can write f(n) ∈ Θ(g(n)) to indicate that f(n) is an element of Θ(g(n)). But we generally write f(n) = Θ(g(n)) to express the same notation.

g(n) is an ** asymptotically tight bound** for f(n), if the function f(n) is equal to g(n) to within a constant factor. Also, as per the definition, every member f(n) ∈ Θ(g(n)) should be

**i.e., f(n) be nonnegative whenever n is sufficiently large.**

*asymptotically nonnegative*# Ο (big oh) notation

When we have only an asymptotic upper bound on a function, we use Ο notation. So, for a given function g(n), we denote by Ο(g(n)) the set of functions

Ο(g(n)) = {f(n): there exists positive constants c and n_{0}such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n_{0}}

In the above figure, for all values of n, at and to the right of n_{0}, the value of the function f(n) is on or below cg(n).

Note that f(n) = Θ(g(n)) implies f(n) = Ο(g(n)), since Θ notation is a stronger notion than Ο notation. As per set theory we can write it as Θ(g(n)) ⊆ Ο(g(n)). With Ο notation, we are just saying that for some constant multiple of g(n) is an asymptotic upper bound on f(n), with no guarantee of how tight an upper bound it is.

# Ω (big omega) notation

This notation provides an ** asymptotic lower bound** on a function. For a given function g(n), we denote by Ω(g(n)) the set of functions

Ω(g(n)) = {f(n): there exist positive constants c and n_{0}such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n_{0}}

In the above figure, for all values n at or to the right of n_{0}, the value of f(n) is on or above cg(n).

For any two functions f(n) and g(n), we have f(n) = Θ(g(n) if and only if f(n) = Ο(g(n)) and f(n) = Ω (g(n)).