Big Omega (W) Notation in Data Structure | DSA Tutorials

The lower bound for the function f is provided by the big omega notation ($\Omega$).

What is Big Omega ($\Omega$) – Definition

Considering g to be a function from the non-negative integers into the positive real numbers. The $\Omega$(g) is the set of functions f, also from the non-negative integers into the positive real numbers, such that for some real constant c >= 0 and some non-negative integer constant n₀, f(n) >= c g(n) for all n >= n₀.

For all values of n < n₀, the function f is at most c times the function g. Here, g provides a lower bound, by some constant multiple, on the value of for all suitable large n (i.e., n >= n₀).

In general: $\Omega$(g (n)) = {f(n): there exists positive constants c and n₀ such that 0 <= c g (n) <= f(n) for all n, n >= n₀}.

Let’s take some examples of functions and find the Big Omega Notations.

Constant Function

Consider the following constant functions:

• f(n) = 16
• f(n) = 27
• f(n) = 1627

Then, for satisfying the big omega condition, the above functions can be expressed as:

f(n) >= 15 * 1, where c = 15, and n₀ = 0, So f(n) = $\Omega$(1) for the above function.
f(n) >= 26 * 1, where c = 26, and n₀ = 0, So f(n) = $\Omega$(1) for the above function.
f(n) >= 1626 * 1, where c = 1626, and n₀ = 0, So f(n) = $\Omega$(1) for the above function.

Linear Function

Consider the following linear functions.

• f(n) = 3n + 5
• f(n) = 2n + 3
• f(n) = 7n + 5

f(n) = 3n + 5
3n < 3n + 5 for all ‘n’. {c = 3}
Thus, f(n) = $\Omega$(n)

f(n) = 2n + 3
2n < 2n + 3 for all n. {c = 2}
Thus, f(n) = $\Omega$(n)

f(n) = 7n + 5
7n < 7n + 5 for all n. {c = 7}
Thus, f(n) = $\Omega$(n)

Quadratic Function

Consider the following quadratic functions:

• f(n) = 27n² + 16n
• f(n) = 27n² + 16
• f(n) = 10n² + 7
• f(n) = 27n² + 16n + 25

f(n) = 27n² + 16n
27n² < 27n² + 16n, for all n, {c = 27}.
So, f(n) = $\Omega$(n²)

f(n) = 27n² + 16
27n² < 27n² + 16, for all n, {c = 27}.
So, f(n) = $\Omega$(n²)

f(n) = 10n² + 7
10n² < 10n² + 7, for all n, {c = 10}.
So, f(n) = $\Omega$(n²)

f(n) = 27n² + 16n + 25
27n² < 27n² + 16n + 25, for all n, {c = 27}.
So, f(n) = $\Omega$(n²)

Cubic Function

Consider the following cubic functions:

• f(n) = 2n³ + n² + 2n
• f(n) = 4n³ + 2n + 3

f(n) = 2n³ + n² + 2n
2n³ < 2n³ + n² + 2n, for all n, {c=2}
So, f(n) = $\Omega$(n³)

f(n) = 4n³ + 2n + 3
4n³ < 4n³ + 2n + 3, for all n, {c=4}
So, f(n) = $\Omega$(n³)

Exponential Function

Consider the following exponential functions:

• f(n) = 2ⁿ + 6n² + 3n
• f(n) = 4 * 2ⁿ + 3n

f(n) = 2ⁿ + 6n² + 3n
2ⁿ < 2ⁿ + 6n² + 3n, for all n, {c=1}
So, f(n) = $\Omega$(2ⁿ)

f(n) = 4 * 2ⁿ+ 3n
4 * 2ⁿ < 4 * 2ⁿ+ 3n, for all n, {c=1}
So, f(n) = $\Omega$(2ⁿ)