Big Theta (θ) Notation

When learning about algorithms in computer science, we want to know how fast or slow a program runs. For that, we use something called asymptotic notations.

You've already learned about:

• Big-O Notation → Worst-case performance

• Big-Omega (Ω) Notation → Best-case performance

Now let’s understand the most balanced one:
Big-Theta (Θ) Notation

What is Big-Theta (Θ) Notation?

Big-Theta (Θ) notation gives us the average case or the exact growth rate of an algorithm — not just the best or worst.

It shows us both:

• The minimum time an algorithm might take

• The maximum time it might take

So, it tells us the true running time for most inputs when the input size n becomes large.

Definition of Θ(g(n)):

Let’s break it down:
 If you have a function f(n), and you can find two constants c₁ and c₂ such that:

c₁ × g(n) ≤ f(n) ≤ c₂ × g(n) for all n ≥ n₀,

then we say:

f(n) = Θ(g(n))

It means:
 f(n) stays between two multiples of g(n) as n becomes very large.

Graphical Meaning:

In the graph:

• f(n) is the actual time the algorithm takes

• g(n) is the reference function (like n, n², log n, etc.)

Big-Theta says:
 f(n) is trapped between two curves — c₁ * g(n) and c₂ * g(n)
This gives a tight bound or an exact idea of how the algorithm grows.

Real-Life Example:

Think of a bus journey:

• The worst-case time is if there's heavy traffic (Big-O)

• The best-case time is if roads are clear (Big-Ω)

• The average time considering regular traffic = Big-Theta (Θ)

Big-Theta gives a realistic estimate of how long it will usually take.

How to Find Big-Theta (Θ):

To calculate the average time complexity of an algorithm using Θ notation, follow these steps:

1. Break the program into smaller parts
   
   

2. Check how many operations each part performs
   
   

3. Assume average inputs (not worst or best case)
   
   

4. Add all operations, then divide by the number of inputs
   
   

5. Ignore constants, and write it as Θ(g(n))
   
   

Example:
If a loop runs (n² + n) times in average input, we ignore smaller and constant terms:
→ Final answer: Θ(n²)

Summary:

Final Thought

Big-Theta (Θ) Notation is like saying: “This is how long the algorithm usually takes — not too fast, not too slow.”
It gives a realistic, tight estimate of performance, which is very useful for programmers.