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).
- We look at the loop: runs
-
Space Complexity:
- Only a few variables (
max_val
,num
) used. - No extra data structures proportional to
n
. - Total space: O(1).
- Only a few variables (
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 |
Top comments (0)