You've learned about Big-O notation for analyzing worst-case time complexity. But what if you want to describe the best case or the average case? What if you want to give exact bounds instead of just upper bounds?

This is where asymptotic notation comes in. It's a complete mathematical framework for describing algorithm performance.

Asymptotic notation is a set of mathematical tools to describe how algorithms behave as input size approaches infinity.

Why Multiple Notations?

Imagine describing a car's speed:

Big-O (O): "The car will never go faster than 120 mph"
Big-Omega (Ω): "The car will never go slower than 40 mph"
Big-Theta (Θ): "The car typically runs between 60-70 mph"

Similarly, in algorithm analysis:

Big-O: Upper bound (worst case)
Big-Omega: Lower bound (best case)
Big-Theta: Tight bound (average case)

Key Idea: Different notations describe different aspects of algorithm performance. Big-O is most common, but the others provide valuable insights too.

The Three Main Notations

Overview Table

Notation	Meaning	Describes	Example
Big-O (O)	Upper bound	Worst case	"At most this slow"
Big-Omega (Ω)	Lower bound	Best case	"At least this fast"
Big-Theta (Θ)	Tight bound	Average case	"Exactly this performance"

Big-O Notation (O) - Upper Bound

Definition: f(n) = O(g(n)) means f(n) grows no faster than g(n).

Meaning: The algorithm will never be slower than this bound.

Real-World Analogy: "I'll arrive in at most 2 hours" - you might arrive earlier, but never later than 2 hours.

Example: Linear Search

Python

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Best case: O(1) - target is first element
# Average case: O(n/2) → O(n)
# Worst case: O(n) - target is last or not present
# 
# Big-O describes worst case: O(n)

Analysis:

›We say linear search is O(n)
›This means: "In the worst case, it takes at most n steps"
›It might be faster (O(1) best case), but never slower than O(n)

Common Big-O Examples

Python

# O(1) - Constant
def get_first(arr):
    return arr[0]  # Always 1 step

# O(n) - Linear
def print_all(arr):
    for item in arr:
        print(item)  # n steps

# O(n²) - Quadratic
def print_pairs(arr):
    for i in arr:
        for j in arr:
            print(i, j)  # n × n steps

Big-Omega Notation (Ω) - Lower Bound

Definition: f(n) = Ω(g(n)) means f(n) grows at least as fast as g(n).

Meaning: The algorithm will never be faster than this bound.

Real-World Analogy: "I'll arrive in at least 1 hour" - you might arrive later, but never earlier than 1 hour.

Example: Linear Search

Python

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Best case: Ω(1) - find target immediately
# This is the FASTEST it can possibly be
# 
# Big-Omega: Ω(1)

Analysis:

›We say linear search is Ω(1)
›This means: "In the best case, it takes at least 1 step"
›It might be slower (O(n) worst case), but never faster than Ω(1)

Comparison: Big-O vs Big-Omega

Python

def find_max(arr):
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

# Must check EVERY element
# Best case: Still checks all n elements → Ω(n)
# Worst case: Checks all n elements → O(n)
# 
# Big-O: O(n) - "at most n steps"
# Big-Omega: Ω(n) - "at least n steps"

Key Insight: Finding maximum always takes n steps (can't skip any element), so Big-O and Big-Omega are the same: O(n) and Ω(n).

Big-Theta Notation (Θ) - Tight Bound

Definition: f(n) = Θ(g(n)) means f(n) grows at the same rate as g(n).

Meaning: The algorithm performs exactly at this rate (both upper and lower bounds match).

Real-World Analogy: "I'll arrive in exactly 1.5 hours" - not faster, not slower, right at 1.5 hours.

Mathematical Definition: f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) AND f(n) = Ω(g(n))

Example: Print All Elements

Python

def print_all(arr):
    for item in arr:
        print(item)

# Best case: Must print all n elements → Ω(n)
# Worst case: Prints all n elements → O(n)
# Always exactly n steps
# 
# Big-Theta: Θ(n)

Analysis:

›We say print_all is Θ(n)
›This means: "Always takes exactly n steps"
›Both best and worst cases are the same: n steps

When Big-Theta Applies

Big-Theta is used when the algorithm's performance is consistent regardless of input.

Python

# Θ(n²) - Always n² iterations
def nested_loops(n):
    for i in range(n):
        for j in range(n):
            print(i, j)

# Θ(n) - Always n additions
def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

# Θ(1) - Always 1 operation
def get_first(arr):
    return arr[0]

Complete Analysis Example

Let's analyze a complete algorithm with all three notations:

Python

def search_and_print(arr, target):
    # First: Linear search
    found_index = -1
    for i in range(len(arr)):
        if arr[i] == target:
            found_index = i
            break
    
    # Second: Print all elements up to found index
    if found_index != -1:
        for i in range(found_index + 1):
            print(arr[i])

# ANALYSIS:
# Best case: target at index 0
#   - Search: 1 comparison
#   - Print: 1 element
#   - Total: Ω(1)
#
# Worst case: target at last index or not present
#   - Search: n comparisons
#   - Print: n elements (if found) or 0 (if not found)
#   - Total: O(n)
#
# Average case: target in middle
#   - Total: Θ(n)

Comparison of All Three Notations

Algorithm	Big-O (Worst)	Big-Omega (Best)	Big-Theta (Tight)
Linear Search	O(n)	Ω(1)	No tight bound
Binary Search	O(log n)	Ω(1)	No tight bound
Find Maximum	O(n)	Ω(n)	Θ(n)
Bubble Sort	O(n²)	Ω(n)	No tight bound
Merge Sort	O(n log n)	Ω(n log n)	Θ(n log n)
Print Array	O(n)	Ω(n)	Θ(n)
Access Array[i]	O(1)	Ω(1)	Θ(1)

Key Observations:

›Θ(n) exists when O(n) = Ω(n) (best and worst cases match)
›Linear search has different best/worst cases, so no tight bound
›Merge sort always takes n log n steps, so Θ(n log n)

Graphical Understanding

Imagine plotting algorithm runtime vs input size:

Big-O (O): The curve will never go above this line
Big-Omega (Ω): The curve will never go below this line
Big-Theta (Θ): The curve stays between two parallel lines

Runtime
   ^
   |     O(n²) upper bound
   |    /
   |   /  Actual curve (could be anywhere below)
   |  /
   | /
   |/___________________> Input size (n)


Runtime
   ^
   |
   |    Actual curve (could be anywhere above)
   |   /
   |  /
   | /   Ω(n) lower bound
   |/___________________> Input size (n)


Runtime
   ^
   |     O(n) upper bound
   |    ==================
   |   /  Θ(n) tight bound
   |  /
   | /   Ω(n) lower bound
   |==================___> Input size (n)

Formal Mathematical Definitions

Big-O (Upper Bound)

f(n) = O(g(n)) if there exist constants c and n₀ such that:

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

Example: f(n) = 3n + 5 is O(n)

›Choose c = 4, n₀ = 5
›For n ≥ 5: 3n + 5 ≤ 4n

Big-Omega (Lower Bound)

f(n) = Ω(g(n)) if there exist constants c and n₀ such that:

f(n) ≥ c × g(n) for all n ≥ n₀

Example: f(n) = 3n + 5 is Ω(n)

›Choose c = 3, n₀ = 1
›For n ≥ 1: 3n + 5 ≥ 3n

Big-Theta (Tight Bound)

f(n) = Θ(g(n)) if there exist constants c₁, c₂, and n₀ such that:

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

Example: f(n) = 3n + 5 is Θ(n)

›Choose c₁ = 3, c₂ = 4, n₀ = 5
›For n ≥ 5: 3n ≤ 3n + 5 ≤ 4n

Little-o and Little-omega

Two additional notations for strict bounds:

Little-o (o) - Strict Upper Bound

f(n) = o(g(n)) means f(n) grows strictly slower than g(n)

Example:

›n = o(n²) ✓ (n grows slower than n²)
›n² = o(n²) ✗ (same growth rate, not strictly slower)

Little-omega (ω) - Strict Lower Bound

f(n) = ω(g(n)) means f(n) grows strictly faster than g(n)

Example:

›n² = ω(n) ✓ (n² grows faster than n)
›n² = ω(n²) ✗ (same growth rate, not strictly faster)

Common Mistakes to Avoid

Mistake 1: Confusing O with Θ

Wrong: "Linear search is O(1) in the best case"
Right: "Linear search is Ω(1) in the best case, O(n) in the worst case"

Big-O describes worst case, not best case!

Mistake 2: Using O for Everything

Wrong: "This algorithm is O(n)"
Better: "Worst case: O(n), Best case: Ω(1), Average: Θ(n)"

Provide complete analysis when possible!

Mistake 3: Ignoring Tight Bounds

Python

def print_n_times(n):
    for i in range(n):
        print(i)

# Complete analysis:
# O(n) - True, but not precise
# Ω(n) - True
# Θ(n) - Best answer (tight bound)

Practice Problems

Problem 1: Analyze This Algorithm

Python

def mystery(arr):
    n = len(arr)
    
    # Part 1
    for i in range(n):
        print(arr[i])
    
    # Part 2
    for i in range(n):
        if arr[i] == 0:
            return True
    
    return False

# What are O, Ω, and Θ?

Answer:

›Best case: 0 at first position after printing all → Ω(n)
›Worst case: No 0 in array, checks all elements → O(n)
›Tight bound: Both cases are O(n) and Ω(n) → Θ(n)

Problem 2: Which Notation?

For each algorithm, determine if it has a tight bound (Θ):

›Binary search: O(log n), Ω(1) → No Θ (best ≠ worst)
›Merge sort: O(n log n), Ω(n log n) → Yes, Θ(n log n)
›Linear search: O(n), Ω(1) → No Θ (best ≠ worst)
›Print array: O(n), Ω(n) → Yes, Θ(n)

Key Takeaways

Big-O (O): Upper bound - worst case performance

Big-Omega (Ω): Lower bound - best case performance

Big-Theta (Θ): Tight bound - exact performance (when upper = lower)

Complete analysis: State all three when analyzing algorithms

Most common: Big-O is used most often in practice

Most precise: Big-Theta gives the most accurate description

What's Next?

Now that you understand all asymptotic notations:

›Master Theorem - Analyze divide-and-conquer algorithms
›Recursion Tree Method - Visual complexity analysis
›Array Algorithms - Apply these concepts to real algorithms

Summary Table

Notation	Symbol	Meaning	Use Case
Big-O	O	≤ (at most)	Worst case, upper bound
Big-Omega	Ω	≥ (at least)	Best case, lower bound
Big-Theta	Θ	= (exactly)	Tight bound, average case
Little-o	o	< (strictly less)	Strict upper bound
Little-omega	ω	> (strictly more)	Strict lower bound

Practice Exercise

Analyze this sorting check algorithm:

Python

def is_sorted(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True

# Determine O, Ω, and Θ
# Answer:
# Best: Ω(1) - first two elements out of order
# Worst: O(n) - array is sorted, check all
# Tight: No Θ (best ≠ worst)

Ready to continue? Let's explore Master Theorem for analyzing recursive algorithms!

←

PreviousSpace Complexity

NextAnalyze Code Complexity

→