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 c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}

A function f(n) belongs to the set Θ(g(n)) if there exist positive constants c₁ and c₂ such that it can be “sandwiched” between c₁g(n) and c₂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 asymptotically nonnegative i.e., f(n) be nonnegative whenever n is sufficiently large.

Ο (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 n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}

In the above figure, for all values of n, at and to the right of n₀, 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 n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0}

In the above figure, for all values n at or to the right of n₀, 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)).