Big O, Theta, Omega Notations — What do they mean?

These are asymptotic notations used to describe how the runtime or space requirement of an algorithm grows as the input size (n) grows large. They help you understand the efficiency of algorithms, especially for large inputs.

Big O Notation (O) — Upper Bound

What it means: Big O describes the worst-case upper bound on an algorithm's growth rate.
It tells you the maximum time or space the algorithm could take in the worst scenario.
Example: If an algorithm is O(n²), it means in the worst case, the time it takes grows at most proportional to the square of input size.

Visual analogy:
Think of Big O as saying: "The algorithm will take no longer than this time."

Omega Notation (Ω) — Lower Bound

What it means: Omega describes the best-case lower bound on the algorithm's growth rate.
It tells you the minimum time or space the algorithm requires.
Example: Ω(n) means the algorithm will take at least linear time for large enough inputs.

Visual analogy:
Think of Omega as: "The algorithm will take at least this much time."

Theta Notation (Θ) — Tight Bound

What it means: Theta means the algorithm's runtime or space is asymptotically tight bound — it grows exactly proportional to a function.
It gives a both upper and lower bound.
Example: Θ(n log n) means the runtime grows proportional to n log n in both worst and best cases (ignoring constant factors).

Visual analogy:
Think of Theta as: "The algorithm runs roughly this time."

Summary Table

Notation	Describes	Bound Type	Example
O(f(n))	Worst case upper bound	Upper bound	O(n²) — max growth
Ω(f(n))	Best case lower bound	Lower bound	Ω(n) — min growth
Θ(f(n))	Tight bound (best = worst)	Both bounds	Θ(n log n) — tight fit

2. Time Complexity

Measures how running time of an algorithm grows as the input size increases.
Usually expressed in Big O notation (worst case).
Important for predicting performance on large inputs.

Examples:

Algorithm Type	Time Complexity	Description
Constant time	O(1)	Takes the same time regardless of input size
Linear time	O(n)	Time grows proportionally with input size
Quadratic time	O(n²)	Nested loops, time grows with square of input
Logarithmic time	O(log n)	Dividing problem size each step (e.g., binary search)
Linearithmic time	O(n log n)	Typical of efficient sorting algorithms (merge sort)

3. Space Complexity

Measures how much extra memory an algorithm needs as input size grows.
Also described in Big O notation.
Helps understand memory efficiency, crucial for large datasets or limited-memory environments.

Examples:

O(1) space: Uses a fixed amount of memory regardless of input size (e.g., swapping two variables).
O(n) space: Uses memory proportional to input size (e.g., creating a copy of an input array).

4. Putting it all together: Example

Let's consider a function that finds the maximum number in a list:

def find_max(arr):
    max_val = arr[0]          # O(1) operation
    for num in arr:           # Runs n times
        if num > max_val:     # O(1) operation each time
            max_val = num
    return max_val

Time Complexity:
- We look at the loop: runs n times.
- Each iteration is O(1).
- Total time: O(n).
Space Complexity:
- Only a few variables (max_val, num) used.
- No extra data structures proportional to n.
- Total space: O(1).

5. Important notes and best practices

Ignore constants: O(2n) = O(n). We focus on dominant terms as input size grows.
Worst-case vs average-case: Big O often means worst-case unless specified.
Input size matters: These notations make sense as n → ∞.
Space vs time tradeoff: Sometimes faster algorithms use more space.
Use Big O to compare algorithms: e.g., O(n log n) is better than O(n²) for large n.

6. Visual intuition

Input size n	O(1)	O(log n)	O(n)	O(n log n)	O(n²)
10	1	~3	10	30	100
100	1	~7	100	700	10,000
1000	1	~10	1000	10,000	1,000,000

7. Summary

Concept	Description
Big O (O)	Upper bound — worst case runtime or space growth
Omega (Ω)	Lower bound — best case runtime or space growth
Theta (Θ)	Tight bound — exact asymptotic runtime or space growth
Time complexity	How algorithm runtime grows as input size grows
Space complexity	How algorithm memory usage grows as input size grows