Big-O, Big-Theta, and Big-Omega Notations

In the previous lesson, we understood time and space complexity and why efficiency matters.

Now we need a standard language to describe how fast or slow an algorithm grows as input size increases.

That standard language is provided by asymptotic notations.

The three most important ones are:

Big-O (O), Big-Theta (Θ), and Big-Omega (Ω).

Why Do We Need Asymptotic Notations?

When we analyze algorithms, we do not care about:

• Exact execution time in seconds
• Hardware speed
• Programming language

Instead, we care about how performance grows as input size becomes very large.

Asymptotic notations allow us to ignore small details and focus on long-term behavior.

Big-O Notation (Upper Bound)

Big-O notation describes the worst-case growth of an algorithm.

It answers this question:

“What is the maximum time an algorithm might take for a given input size?”

This is the most commonly used notation in interviews and real systems.

Example: Linear Search

Consider searching for a value in an unsorted list:

arr = [3, 7, 2, 9, 5]
target = 9

for x in arr:
    if x == target:
        break

In the worst case, the value is at the end of the list or not present at all.

The loop checks every element, so the time grows linearly with input size.

This algorithm has:

Big-O = O(n)

Big-Theta Notation (Tight Bound)

Big-Theta represents the exact growth rate of an algorithm.

It is used when the best case and worst case grow at the same rate.

It answers:

“How does the algorithm actually grow?”

Example: Printing All Elements

Consider this code:

arr = [4, 6, 8, 1]

for x in arr:
    print(x)

No matter what values are inside, the loop always runs exactly n times.

There is no faster or slower case.

So the complexity is:

Big-Theta = Θ(n)

Big-Omega Notation (Lower Bound)

Big-Omega describes the best-case growth of an algorithm.

It answers:

“What is the minimum time the algorithm will take?”

This notation is useful when we want to know how fast an algorithm can possibly run.

Example: Best Case in Linear Search

If the target is the first element:

arr = [9, 3, 7, 5]
target = 9

if arr[0] == target:
    print("Found")

The algorithm finishes immediately, regardless of array size.

So the best case is:

Big-Omega = Ω(1)

Comparing the Three Notations

Think of these notations like this:

• Big-O → Worst performance guarantee
• Big-Theta → Exact performance growth
• Big-Omega → Best possible performance

Most real-world systems are designed using Big-O to ensure reliability.

Real-World Analogy

Imagine driving to work:

Best case (Ω): no traffic, green signals.

Worst case (O): heavy traffic, accidents, roadblocks.

Average behavior lies somewhere in between, but planners design for the worst case.

Mini Practice

Think about this:

• If an algorithm always runs n times, which notation fits best?
• If an algorithm may stop early, which notations apply?

Exercises

Quick Quiz

In the next lesson, we will apply these notations to perform a mathematical analysis of algorithms using real examples.