Big Theta Notation in Data Structure | DSA Tutorials

The lower and upper bound for the function f is provided by the big theta notation ($\Theta$).

Big Theta ($\Theta$) Notation – Definition

Considering g to be a function from the non-negative integers into the positive real numbers. The $\Theta$(g) = O(g) $\cap$ $\Omega$(g), that means, the set of functions that are both in O(g) and $\Omega$(g). The $\Theta$(g) is the set of functions f such that for some positive constants c₁ and c₂, and an n₀ exists such that c₁g(n) <= f(n) <= c₂g(n) for all n, n>= n₀. By f $\in$ $\Theta$(g) means f is of order g.

Constant Function

Consider the following constant functions:

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

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

15 * 1 <= f(n) <= 16 * 1, where c₁ = 15, c₂ = 16 and n₀ = 0, So f(n) = $\Theta$(1) for the above function.
26 * 1 <= f(n) <= 27 * 1, where c₁ = 26, c₂ = 27 and n₀ = 0, So f(n) = $\Theta$(1) for the above function.
1626 * 1 <= f(n) <= 1627 * 1, where c₁ = 1626, c₂ = 1627 and n₀ = 0, So f(n) = $\Theta$(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}
also, 3n + 5 <= 4n for n >= 5, c₂ = 4, n₀ = 5
thus,
3n < 3n + 5 <= 4n for c₁ = 3, c₂ = 4, n₀=5
Thus, f(n) = $\Theta$(n)

f(n) = 2n + 3
2n < 2n + 3 for all ‘n’. {c₁ = 2}
also, 2n + 3 <= 3n for n >= 3, c₂ = 3, n₀ = 3
Thus, f(n) = $\Theta$(n)

f(n) = 7n + 5
7n < 7n + 5 for all ‘n’. {c₁ = 7}
also, 7n + 5 <= 8n for n >= 5, c₂ = 8, n₀ = 5
Thus, f(n) = $\Theta$(n)

Quadratic Function

Consider the following quadratic functions:

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

f(n) = 27n² + 16n
27n² < 27n² + 16n, for all n, {c₁ = 27}.
also
27n² + 16n <= 28n² for n >= n₀ = 16, c₂ = 28
thus, 27n² <= 27n² + 16n <= 28n² for c₁ = 27, c₂ = 28, n₀ = 16
So, f(n) = $\Theta$(n²)

f(n) = 27n² + 16
27n² < 27n² + 16, for all n, {c₁ = 27}.
also
27n² + 16 <= 28n² for n >= n₀ = 16, c₂ = 28
thus, 27n² <= 27n² + 16 <= 28n² for c₁ = 27, c₂ = 28, n₀ = 8
So, f(n) = $\Theta$(n²)

f(n) = 10n² + 7
10n² < 10n² + 7, for all n, {c₁ = 10}.
also
27n² + 7n <= 11n² for n >= n₀ = 7, c₂ = 11
thus, 10n² <= 10n² + 7 <= 11n² for c₁ = 10, c₂ = 11, n>=n₀ = 7
So, f(n) = $\Theta$(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>= n₀, {c₁=2}
also, 2n³ + n² + 2n <= 3n³, for all n>= n₀ = 2, {c₂=3}
thus, 2n³ < 2n³ + n² + 2n <= 3n³, for all n>= n₀ = 2, c₁=2, c₂=3
So, f(n) = $\Theta$(n²)

f(n) = 4n³ + 2n + 3
4n³ < 4n³ + 2n + 3, for all n, {c=4}
So, f(n) = $\Theta$(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>= n₀, {c₁=1}
also 2ⁿ + 6n² + 3n <= 8 * 2ⁿ for all n>= n₀ >= 4, {c₂=8}
thus 2ⁿ < 2ⁿ + 6n² + 3n <= 8 * 2ⁿ, for all n>= n₀, {c₁=1, c₂ = 8}
So, f(n) = $\Theta$(2ⁿ)

f(n) = 4 * 2ⁿ+ 3n
4 * 2ⁿ < 4 * 2ⁿ + 3n, for all n>= n₀, {c₁=4}
also 4 * 2ⁿ + 3n <= 7 * 2ⁿ for all n>= n₀ >= 1, {c₂=7}
thus 4 * 2ⁿ < 4 * 2ⁿ + 3n <= 7 * 2ⁿ, for all n>= n₀ = 1, {c₁=4, c₂ = 5}
So, f(n) = $\Theta$(2ⁿ)