Asymptotic Notations: Θ , O, Ω , o,ω Notations and Their Properties

Asymptotic Notation

Having the expression for best, average case and worst cases, for all the three cases, we need to identify the upper and lower bounds. In order to represent these upper and lower bounds, we need some kind of syntax and that is the subject of following discussion. Let us assume that the given algorithm is represented in the form of the function f(n).

Big -O Notation

This notation gives the tight upper bound of the given function. Generally, it is represented as f(n) = O(g(n)). That means, at larger values of n, the upper bound of f(n) is g(n). For example: if f(n) = n⁴ + 100n² + 10n + 50 is the given algorithm, then n⁴ is g(n). i.e. g(n) gives the maximum rate of growth for f(n) at larger values of n.

Let us see the O-notation with little more detail. O-notation defined as O(g(n)) = {f(n): there exist positive constants c and n_o such that 0 <= f(n) <= cg(n) for all n >= n₀ }. g(n) is an asymptotic tight upper bound for f(n). Our objective is to give the smallest rate of growth g(n) which is greater than or equal to the given algorithm’s rate of growth f(n).

In general, we discard lower values of n. That means the rate of growth at lower values of n is not important. In the below figure, n₀ is the point from which we need to consider the rate of growths for a given algorithm. Below n₀, the rate of growths could be different.

Examples:

1. f(n) = 3n + 8

Solution: 3n +8 <= 4n for all n >= 1

So, 3n + 8 = O(n) with c = 4 and n₀ = 8

2. f(n) = 2n^{3 –} 2n²

Solution: 2n^{3 –} 2n² <= 2n³ for all n >= 1

So, 2n^{3 –} 2n² = O(n³) with c = 2 and n₀ = 1

3. f(n) = n

Solution: n <= n² for all n >= 1

So, n = O(n²) with c = 1 and n₀ = 1

Big - Ω Notation

Similar to the O discussion, this notation gives the tighter lower bound of the given algorithm and we represent it as f(n) =Ω(g(n)). That means, at larger values of n, the tighter lower bound of f(n) is g(n). For example, if f(n) = 100n² + 10n + 50, g(n) is omega(n²).

Fig: Big - Omega Notation

The Ω notation can be defined as Ω(g(n)) = { f(n): there exists positive constants c and n₀ such that 0 <= cg(n) <= f(n) for all n >= n₀ }. g(n) is an asypmtotic tight lower bound for f(n). Our objective is to give the largest rate of growth g(n) which is less or equal to given algorithm’s rate of growth f(n).

Examples:

1. f(n) = 5n²

Solution: There exists c, n₀ such that: 0 <= cn <= 5n² => cn <= 5n² => c = 1 and n₀ = 1

So, 5n² = Ω(n) with c = 1 and n₀ = 1.

Similarly, n³ = Ω(n²), n = Ω(logn)

Big – Θ Notation

This notation decides whether the upper and the lower bounds or a given function (algorithm) are same or not. The average running time of algorithm is always between lower bound and upper bound. If the upper bound (O) and the lower bound (Ω) gives the same result, then Θ notation will also give the same rate of growth.

As an example, lets take f(n) = 10n + n. Then, its tight upper bound g(n) is O(n). The rate of growth in the base case is g(n) = O(n). In this case, rate of growths in best case and the worst case are the same. As a result, the average case will also be same. For a given function (algorithm), if the rate of growths (bounds) for O and Ω are not same, then the rate of growth Θ also varies.

Now, lets consider the definition of Θ notation. It is defined as Θ(g(n)) = { f(n): there exist positive constants c₁, c₂ and n₀ such that 0 <= c₁g(n) <= f(n) <= c₂g(n) for all n >= n₀. g(n) is an asymptotic tight bound for f(n). Θ(g(n)) is the set of functions with the same order of growth as g(n).

Examples:

1. f(n) = n²/2 – n/2

Solution: n²/5 <= n²/2 – n/2 <= n² for all n >= 1

So, n²/2 – n/2 = Θ(n²) with c₁ = 1/5, c₂ = 1 and n₀ = 1

2. Prove that f(n) != Θ(logn)

Solution: c₁logn <= n <= c₂logn => c₂ >= n/logn, for all n >= n₀, which is impossible.

References:

1. L, Robert. "Data Structures and Algorithms in24Hours"

2. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

3.Karumanchi, N. "Data Structures and Algorithms Made Easy"