Big O Notation and Algorithm Analysis

What is Big O Notation?

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards infinity. In computer science, it’s used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Common Time Complexities

O(1) - Constant Time

Operations that take the same amount of time regardless of input size.

def get_first_element(arr):
    return arr[0]  # O(1)

O(log n) - Logarithmic Time

Algorithms that reduce the problem size by a constant factor at each step.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

O(n) - Linear Time

Algorithms that process each element once.

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

O(n log n) - Linearithmic Time

Common in efficient sorting algorithms.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)  # O(n log n) overall

O(n²) - Quadratic Time

Nested iterations over the data.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):  # O(n²)
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

O(2ⁿ) - Exponential Time

Algorithms that generate all subsets or solve problems with brute force.

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)  # O(2ⁿ)

Space Complexity

Space complexity analyzes the amount of memory an algorithm uses relative to input size.

Examples:

• O(1) space: Using a fixed number of variables
• O(n) space: Creating an array proportional to input size
• O(log n) space: Recursive algorithms with logarithmic depth

Big O Rules

1. Drop Constants: O(2n) = O(n)
2. Drop Non-Dominant Terms: O(n² + n) = O(n²)
3. Different Variables: O(a + b) ≠ O(n)
4. Nested Loops: Multiply complexities

Analyzing Algorithms

Step-by-step approach:

1. Identify the input size (n)
2. Count the operations
3. Express as a function of n
4. Simplify using Big O rules

Example Analysis:

def has_duplicate(arr):  # n = len(arr)
    seen = set()         # O(1)
    for num in arr:      # O(n)
        if num in seen:  # O(1) average
            return True
        seen.add(num)    # O(1) average
    return False

# Time Complexity: O(n)
# Space Complexity: O(n)

Common Data Structure Operations

*Average case, assuming balanced tree or good hash function

Best, Average, and Worst Case

• Best Case: Minimum time required (often not useful)
• Average Case: Expected time for random input
• Worst Case: Maximum time required (most important)

Practical Tips

1. Optimize the bottleneck: Focus on the slowest part
2. Trade-offs: Sometimes using more space can reduce time complexity
3. Real-world constraints: Consider actual data sizes
4. Profiling: Measure actual performance

Practice Problems

1. What’s the time complexity of finding all pairs in an array that sum to a target?
2. How can you improve the space complexity of recursive Fibonacci?
3. What’s the complexity of building a heap from an array?