Time & Space Complexity

Understanding how to measure algorithm efficiency is crucial for writing scalable code. Time and space complexity help us quantify how long code takes to run and how much memory it uses.

Why Complexity Matters

Consider two approaches to find if a number exists in a list:

# Approach 1: Linear search - O(n)
def linear_search(arr, target):
    for item in arr:
        if item == target:
            return True
    return False

# Approach 2: Binary search (sorted array) - O(log n)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

For a list of 1 million elements, linear search may check all 1M items, while binary search needs only ~20 comparisons!

Big-O Notation

Big-O describes the upper bound of time/space an algorithm needs as input size grows.

Notation Meaning

• O(1): Constant - same time regardless of input size
• O(log n): Logarithmic - divides problem in half each step
• O(n): Linear - directly proportional to input size
• O(n log n): Log-linear - efficient sorting algorithms
• O(n²): Quadratic - nested loops
• O(2ⁿ): Exponential - very slow, doubles with each additional input

Big-O Complexity Chart

Visual Comparison

Operations for n = 100:
O(1)      →        1 operation
O(log n)  →        7 operations
O(n)      →      100 operations
O(n log n)→      664 operations
O(n²)     →   10,000 operations
O(2ⁿ)     → 1.27 × 10³⁰ operations 😱

Big-Ω (Omega) and Big-Θ (Theta)

Big-Ω (Omega) - Best Case

The lower bound - minimum time an algorithm takes.

Example: Linear search for an element at the beginning

• Best case: O(1) - found immediately
• Big-Ω(1)

Big-Θ (Theta) - Average/Tight Bound

When upper and lower bounds are the same, we use Θ.

Example: Printing all elements

• Always takes exactly n operations
• Θ(n)

Comparison

# Linear Search
# Best case (Ω):    O(1) - element is first
# Average case (Θ): O(n/2) ≈ Θ(n)
# Worst case (O):   O(n) - element is last or not present

Most of the time, we focus on Big-O (worst case) because it guarantees performance.

Common Complexity Classes

Analyzing Code Complexity

Step-by-Step Analysis

def example(arr):
    print(arr[0])           # O(1)
    
    for i in arr:           # O(n)
        print(i)
    
    for i in arr:           # O(n)
        for j in arr:       # O(n) × O(n) = O(n²)
            print(i, j)
    
    # Total: O(1) + O(n) + O(n²) = O(n²)
    # We keep the dominant term

Rules for Calculating Big-O

1. Drop constants: O(2n) → O(n)
2. Drop non-dominant terms: O(n² + n) → O(n²)
3. Different inputs use different variables: O(a + b)
4. Nested loops multiply: O(n * m) for nested loops

Space Complexity

Space complexity measures memory usage as input grows.

Components

1. Input space: Memory for input data
2. Auxiliary space: Extra memory used by algorithm

# O(1) space - only uses a few variables
def sum_array(arr):
    total = 0  # Single variable
    for num in arr:
        total += num
    return total

# O(n) space - creates new array
def double_array(arr):
    result = []  # New array of size n
    for num in arr:
        result.append(num * 2)
    return result

Quiz