Big-Theta Notation (Θ-notation) provides a way to describe the exact bound on the growth rate of an algorithm. It gives both an upper and a lower bound, indicating that the algorithm's performance is tightly bounded within a specific range.

• Purpose: It shows that a function f(n) grows at the same rate as another function g(n) for large input sizes.
• Usefulness: While Big-O tells us the upper bound, Θ-notation provides a more accurate description by showing the algorithm's behavior in both the worst and best cases.

Formal Definition of Big-Theta Notation

A function f(n) is said to be \Theta(g(n)) if there exist positive constants c_1, c_2, and n_0 such that:

c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)

for all n \geq n_0.

• c_1 and c_2 are constants that scale the function g(n).
• n_0 is a threshold value where the inequality holds for all larger values of n.

Understanding Big-Theta Through an Example

Let’s see how to find the \Theta notation for a given function.

Example: f(n) = 3n^2 + 2n + 4

1. Identify the Dominant Term:

   The dominant term here is 3n^2, as it grows faster than 2n and 4 when n becomes large.

2. Choose g(n) as the Dominant Term:

   Let’s set g(n) = n^2. Now we need to find constants c_1, c_2, and n_0 such that:

c_1 \cdot n^2 \leq 3n^2 + 2n + 4 \leq c_2 \cdot n^2

3. Finding Suitable Constants:

   • For the lower bound, we can choose c_1 = 2 and find an n_0 where the inequality holds.
   • For the upper bound, we can choose c_2 = 4 for large enough n.

4. Conclusion:

   Since we have found values of c_1, c_2, and n_0, we can conclude:

f(n) = \Theta(n^2)

How Does Θ-notation Compare with Big-O?

• Big-O Notation: Describes only the upper bound, focusing on the worst-case scenario.
• Θ-Notation: Provides both upper and lower bounds, giving a tighter description of an algorithm’s performance.

Key Properties of Big-Theta

1. Exact Bound: Θ-notation tightly bounds the algorithm within a specific range.
2. Symmetric Bound: It indicates that f(n) grows at the same rate as g(n) for sufficiently large n.
3. Best and Worst Case Covered: While Big-O may overestimate performance, Θ provides a precise characterization.